C. GukiZ ненавидит коробки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Профессор GukiZ не уверен, как он сегодня будет добираться до школы, ведь у него на пути кто-то сложил огромную кучу коробок.

Имеется n куч коробок, расположенных в ряд. В этом ряду i-ая слева куча (1 ≤ i ≤ n) содержит ai коробок. К счастью, m учеников хотят помочь GukiZ убрать коробки с его пути. Ученики работают одновременно. В момент времени 0, все ученики расположены слева от первой кучи. Каждому ученику необходима одна секунда, чтобы передвинуться из этой позиции к первой куче. После этого каждый ученик может выполнять две возможные операции, каждая из которых занимает у него ровно одну секунду. Возможные операции таковы:

  1. Если i ≠ n, студент может переместиться от кучи i к куче i + 1;
  2. Если куча, расположенная перед студентом, непуста, студент может убрать из неё одну коробку.

Ученики GukiZ'а не очень умные, так что им надо, чтобы вы сказали им, как убрать коробки побыстрее (профессор очень нетерпеливый человек и не любит ждать). Они просят вас подсчитать минимальное количество секунд t, за которое они могут убрать все коробки с пути GukiZ'а. Обратите внимание, что по истечении t секунд студенты могут располагаться любым образом, но все коробки к этому моменту должны быть убраны.

Входные данные

В первой строке записано два целых числа, n и m (1 ≤ n, m ≤ 105), количество куч коробок и количество учеников GukiZ'а.

Во второй строке записано n целых чисел a1, a2, ... an (0 ≤ ai ≤ 109), где ai обозначает количество коробок в i-й куче. Гарантируется, что как минимум одна куча непуста.

Выходные данные

В единственной строке выведите одно число — минимальное время, необходимое для того, чтобы убрать все коробки, в секундах.

Примеры
Входные данные
2 1
1 1
Выходные данные
4
Входные данные
3 2
1 0 2
Выходные данные
5
Входные данные
4 100
3 4 5 4
Выходные данные
5
Примечание

Первый пример: ученик должен сначала пройти к первой куче (1 секунда), затем убрать коробку из первой кучи (1 секунда), затем пройти ко второй куче (1 секунда) и наконец, убрать коробку из второй кучи (1 секунда).

Второй пример: одно из оптимальных решений — послать одного ученика, чтобы убрать одну коробку из первой кучи и одну коробку из третьей кучи, и в это же время послать другого студента убрать одну коробку из третьей кучи. Всего на это уйдёт 5 секунд.

Третий пример: в вашем распоряжении много учеников, можно отправить троих из них убрать ящики из первой кучи, четверых из них — убрать ящики из второй кучи, пятерых — убрать ящики из третьей кучи и четверых — убрать ящики из четвертой кучи. Процесс завершится за 5 секунд, когда завершится уборка коробок из последней кучи.