A gas station too far P23800


Statement
 

pdf   zip

html

There is just one road connecting the n+1 cities c0, …, cn consecutively. You want to go from c0 to cn 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 ≤ 105, 0 ≤ sn − 1, and 1 ≤ ℓi ≤ 104.

Output

For every case, print the minimum range for a car to reach cn starting from c0 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++