Question

Splitting Delivery Routes

A logistics company has N packages to deliver, in a fixed order along a single route. The i-th package has weight A_i.

The packages must be split among M delivery vans. Each van carries a contiguous, non-empty group of packages from the route (the route cannot be reordered), and every package must be assigned to exactly one van.

The load of a van is the sum of the weights of the packages it carries. Find the minimum possible value of the maximum load carried by any single van, over all valid ways to split the N packages into exactly M contiguous groups.

Input

The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of packages and the number of vans.

The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression — the weights of the packages, in route order.

Output

Print a single integer — the minimum possible value of the maximum van load.

Example

Example 1:
Input

4 2

10 20 30 40

Output

Explanation
The best split is KaTeX can only parse string typed expression and KaTeX can only parse string typed expression, with loads KaTeX can only parse string typed expression and KaTeX can only parse string typed expression. The maximum load is KaTeX can only parse string typed expression, and no split into 2 groups can do better.

Example 2:
Input

4 1

5 5 5 5

Output

Explanation
With only 1 van, it must carry everything, so the load is the total sum, KaTeX can only parse string typed expression.

Example 3:
Input

4 4

1 2 3 4

Output

Explanation
With exactly as many vans as packages, each van carries exactly one package, so the maximum load is simply the heaviest single package, KaTeX can only parse string typed expression.

Online

Explore Newton School

Recent Questions

Most Solved Questions

Least Solved Questions