There is just one road connecting
the n+1 cities c_{0}, …, c_{n} consecutively.
You want to go from c_{0} to c_{n}
stopping at most s times to fill the tank of the car.
There are gas stations at the cities, but none on the roads.
The length of each road is ℓ_{0}, …, ℓ_{n−1}.
Which is the minimum range for your car?
Suppose that you start with a full tank.

Input

Input consists of several cases.
Every case begins with n and s,
which are followed by n natural numbers ℓ_{0}, …, ℓ_{n−1}.
Suppose 1 ≤ n ≤ 10^{5},
0 ≤ s ≤ n − 1,
and 1 ≤ ℓ_{i} ≤ 10^{4}.

Output

For every case, print the minimum range for a car
to reach c_{n} starting from c_{0}
stopping at most s times to fill the tank.

Hint

Consider a decisional version of this problem.

Public test cases

**Input**

5 0 100 300 500 200 400 5 1 100 300 500 200 400 5 2 100 300 500 200 400 5 3 100 300 500 200 400 5 4 100 300 500 200 400

**Output**

1500 900 600 500 500

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++ Python
- User solutions
- C++ Python