Industry Improvements

Interview

Time limit2sMemory limit1024 MB

Summary

Find the smallest machine capacity that lets all boxes, in their given order, be split into at most k contiguous groups whose weight sums each stay within the capacity.

Level: Medium4 of 10
Topics: Binary search, Greedy, Array
Solved: No attempts yet

Problem

As a member of the Factory Planning Committee, you oversee the production process and make sure everything runs smoothly.

The committee wants the machines on the production line to process boxes without breakdowns. A machine is more likely to break down when it handles heavier objects, so the committee proposes a maximum weight capacity for each machine. Because of budget constraints, the committee also limits the number of times a machine can be started to at most $k$ .

Your task is to find the minimum weight capacity that lets the machine line process all boxes, with the line started at most $k$ times and the boxes processed in the given order.

For example, the boxes can be split into these three contiguous subsequences:

$\{7\}, \{3, 2, 3\}, \{1, 4\}$

With this split, the capacity of the machine needs to be 8 units of weight.

Input

The input consists of:

One line with two integers $n$ and $k$ ( $1 \leq n \leq 10^5$ , $1 \leq k \leq 10^3$ ), the number of boxes and the number of times the machine can be started.
One line with $n$ integers $x$ ( $1 \leq x \leq 10^{10}$ ), the weights of the boxes, in the order in which they need to be processed.

Output

Output the minimum weight capacity required by the machine to process all boxes within $k$ runs or fewer.

Examples3

Example 1
Input
```
6 3
7 3 2 3 1 4
```
Expected output
```
8
```
Example 2
Input
```
4 1
11 18 3 10
```
Expected output
```
42
```

Example 3

Input

5 3
123456789 987654321 111111111 555555555 444444444

Expected output

1098765432