Weidong's minimum working hours

Description

Weidong has $N$ works need to be finished in next $K$ days. Each work costs $N_i$ hours and should be done in one day. (i.e. you cannot split a work into different days). Also, works should be done in the given order. Weidong wants to know what is minimum maximum working hour that he need to work on next $K$ days.

$1 \leq N \leq 10^{5}$ $1 \leq K \leq 10^{9}$ $1 \leq N_i \leq 10^{5}$

Input

For each test case, input consists of $N+1$ lines.

First line contains two number: N K.

In following N lines, each line contains an integer.

Output

One line contains the result.

Sample input 1:

4 2
1
3
2
2

Sample output 1:

4

You can finish 0-th and 1st work to first day, then finish 2nd and 3rd work on second day.