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++
- User solutions
- C++