Problem description

Jasio dostał na urodziny nową grę, której plansza składa się z N kolejno ułożonych pól. Na każdym z pól znajduje się pewna liczba kłujących kolców.

Przed pierwszym polem stoi skoczek, którego zadaniem jest dostanie się za ostatnie pole planszy, wbijając sobie przy tym jak najmniej kolców. W każdym kroku skoczek może przemieścić się na następne pole planszy albo wykonać skok o co najwyżej D pól do przodu. Zgodnie z instrukcją, taki skok może zostać wykonany co najwyżej trzy razy.

Twoim zadaniem jest policzenie minimalnej długości skoku D, takiej że skoczek jest w stanie przejść po planszy, wbijając sobie przy tym co najwyżej K kolców.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz K, będące odpowiednio rozmiarem planszy oraz ograniczeniem na liczbę kolców. W drugim wierszu znajduje się N liczb naturalnych A₁, A₂, …, A_N, gdzie i-ta z nich oznacza liczbę kolców na i-tym polu.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć minimalna (dodatnia) długość skoku D, taka że skoczek jest w stanie przejść po planszy, zbierając przy tym co najwyżej K kolców.

Ograniczenia

1 ≤ N ≤ 100 000, 1 ≤ K, A_i ≤ 10⁹.

Przykład

10 5
3 1 1 4 5 2 1 3 5 1

3

5 2
3 4 5 6 7

6