CF551C.GukiZ hates Boxes

Professor GukiZ is concerned about making his way to school, because massive piles of boxes are blocking his way.

In total there are n piles of boxes, arranged in a line, from left to right, i-th pile (1 ≤ i ≤ n) containing a__i boxes. Luckily, m students are willing to help GukiZ by removing all the boxes from his way. Students are working simultaneously. At time 0, all students are located left of the first pile. It takes one second for every student to move from this position to the first pile, and after that, every student must start performing sequence of two possible operations, each taking one second to complete. Possible operations are:

1. If i ≠ n, move from pile i to pile i + 1;
2. If pile located at the position of student is not empty, remove one box from it.

GukiZ's students aren't smart at all, so they need you to tell them how to remove boxes before professor comes (he is very impatient man, and doesn't want to wait). They ask you to calculate minumum time t in seconds for which they can remove all the boxes from GukiZ's way. Note that students can be positioned in any manner after t seconds, but all the boxes must be removed.

古基兹教授正为如何前往学校而发愁，因为成堆的箱子挡住了他的去路。

总共有 $n$ 堆箱子，从左到右排成一列，其中第 $i$ 堆（$1 \le i \le n$）包含 $a_i$ 个箱子。幸运的是，有 $m$ 名学生愿意帮助古基兹教授，将路上所有箱子全部清除。这些学生将同时工作。在时刻 $0$，所有学生均位于第一堆箱子的左侧。每名学生从该初始位置移动到第一堆箱子需要 $1$ 秒；此后，每名学生必须执行一系列操作，每个操作耗时 $1$ 秒。允许的操作有两种：

1. 若 $i \ne n$，则从第 $i$ 堆移动到第 $i+1$ 堆；
2. 若学生当前所在位置的那堆箱子非空，则从中移除一个箱子。

古基兹教授的学生们并不聪明，因此需要你来告诉他们如何在教授到来前（他非常没有耐心，不愿久等）清除所有箱子。请你计算出清除所有箱子所需的最短时间 $t$（单位：秒）。注意：在 $t$ 秒后，学生可以处于任意位置，但所有箱子必须已被全部清除。

The first line contains two integers n and m (1 ≤ n, m ≤ 105), the number of piles of boxes and the number of GukiZ's students.

The second line contains n integers _a_1, _a_2, ... a__n (0 ≤ a__i ≤ 109) where a__i represents the number of boxes on i-th pile. It's guaranteed that at least one pile of is non-empty.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^5$），分别表示箱子堆的数量和 GukiZ 的学生数量。

第二行包含 $n$ 个整数 $a_1,\ a_2,\ \dots,\ a_n$（$0 \leq a_i \leq 10^9$），其中 $a_i$ 表示第 $i$ 堆箱子的数量。保证至少有一堆箱子非空。

In a single line, print one number, minimum time needed to remove all the boxes in seconds.

在一行中输出一个数字，即移除所有箱子所需的最短时间（单位：秒）。

First sample: Student will first move to the first pile (1 second), then remove box from first pile (1 second), then move to the second pile (1 second) and finally remove the box from second pile (1 second).

Second sample: One of optimal solutions is to send one student to remove a box from the first pile and a box from the third pile, and send another student to remove a box from the third pile. Overall, 5 seconds.

Third sample: With a lot of available students, send three of them to remove boxes from the first pile, four of them to remove boxes from the second pile, five of them to remove boxes from the third pile, and four of them to remove boxes from the fourth pile. Process will be over in 5 seconds, when removing the boxes from the last pile is finished.

第一个样例：学生首先移动到第一堆（1 秒），然后从第一堆移除一个箱子（1 秒），接着移动到第二堆（1 秒），最后从第二堆移除一个箱子（1 秒）。

第二个样例：一种最优方案是：派一名学生分别从第一堆和第三堆各移除一个箱子，同时派另一名学生从第三堆移除一个箱子。整个过程共耗时 5 秒。

第三个样例：当有大量可用学生时，可派三名学生从第一堆移除箱子，四名学生从第二堆移除箱子，五名学生从第三堆移除箱子，四名学生从第四堆移除箱子。整个过程将在第 5 秒结束，此时最后一堆的箱子恰好被全部移除完毕。