A gas station too far P23800

Statement

thehtml

There is just one road connecting the n+1 cities c₀, …, c_n consecutively. You want to go from c₀ 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 ℓ₀, …, ℓ_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 ℓ₀, …, ℓ_n−1. Suppose 1 ≤ n ≤ 10⁵, 0 ≤ s ≤ n − 1, and 1 ≤ ℓ_i ≤ 10⁴.

Output

For every case, print the minimum range for a car to reach c_n starting from c₀ 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

Information

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