/*
Time limit: 5000ms
Memory limit: 256mb

---------------------Copy the following code, complete it and submit---------------------
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/

#include "stdio.h"
#include "stdlib.h"


/**
 * @brief Solve the problem by finding the minimum possible box capacity to dividing items into k boxes
 * @param weights Array containing the weights to be divided
 * @param n Number of weights in the array
 * @param k Number of groups to divide weights into
 * @return Minimum possible value that allows dividing weights into k groups
 */
int solve(int *weights, int n, int k) {
    // WRITE YOUR CODE HERE

}

// DO NOT MODIFY THE CODE BELOW
int main(void) {
    int n, k;
    scanf("%d%d", &n, &k);

    int *weights = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &weights[i]);
    }

    printf("%d\n", solve(weights, n, k));
    
    free(weights);
    return 0;
}


---------------------------------------End of Code---------------------------------------

## Box Packing

There are $n$ items on a production line, where the $i$-th item has weight $w_i$. These items need to be packed into boxes. There are $k$ boxes available, and each box can hold a maximum weight of $x$. Due to the production line constraints, each box can only contain consecutive items. For example, if there are $5$ items that need to be packed into two boxes, then $\{\{1,2,3\}, \{4,5\}\}$ is a valid packing solution, while $\{\{1,5\}, \{2,3,4\}\}$ is not valid.

Find the minimum value of $x$ (maximum weight that each box can hold) such that all $n$ items can be packed into $k$ boxes.

### Input
- First line contains two integers $n$ ($1 \leq n \leq 10^5$) and $k$ ($1 \leq k \leq n$), where $n$ is the number of items and $k$ is the number of boxes.
- Second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($1 \leq w_i \leq 10^4$) representing the weights of the items.

### Output
Output a single integer representing the minimum possible value of $x$ such that all items can be packed into $k$ boxes.

### Example
**Input**
```
5 2
5 4 3 2 1
```

**Output**
```
9
```

**Explanation**

One optimal solution is to pack items $1$, $2$ into the first box (total weight is $9$) and items $3$, $4$, $5$ into the second box (total weight is $6$). Therefore, each box needs to hold at least $9$ units of weight.