GukiZ 教授担心他去学校的路,因为大量的箱子挡住了他的路。
总共有 n 堆盒子,从左到右排成一排,第 i 堆(1 ≤ i ≤ n)包含 a 个盒子。幸运的是,m 位学生愿意帮助 GukiZ,移除他路上的所有盒子。学生们同时工作。在时间 0 时,所有学生都位于第一堆的左侧。每个学生从这个位置移动到第一堆需要一秒钟,之后,每个学生必须开始执行两个可能的操作序列,每个操作需要一秒钟才能完成。可能的操作有:
1、如果i ≠ n,则从i堆移动到i + 1堆;
2. 如果学生所在位置的堆不为空,则从中取出一个盒子。
GukiZ的学生一点也不聪明,所以他们需要你在教授来之前告诉他们如何移除盒子(他是个很不耐烦的人,不想等)。他们要求你计算他们可以移除 GukiZ 路上的所有盒子的最短时间 t(以秒为单位)。请注意,t秒后学生可以以任何方式定位,但必须移除所有盒子。
输入
第一行包含两个整数n和m(1≤n,m≤105),盒子的堆数和GukiZ学生的数量。
第二行包含 n 个整数 a1, a2, ... an (0 ≤ ai ≤ 109),其中 ai 表示第 i 堆盒子的数量。保证至少一堆非空。
输出
在一行中打印一个数字,即移除所有盒子所需的最短时间(以秒为单位)。
示例
输入 #1
2 1 1 1
输出 #1
4
输入 #2
3 2 1 0 2
输出 #2
5
输入 #3
4 100 3 4 5 4
输出 #3
5
注意
第一个示例:学生将首先移动到第一堆(1 秒),然后从第一堆中取出盒子(1 秒),然后移动到第二堆(1 秒),最后从第二堆中取出盒子(1 秒)。
第二个示例:最佳解决方案之一是派一名学生从第一堆中取出一个盒子,从第三堆中取出一个盒子,然后派另一名学生从第三堆中取出一个盒子。总共5秒。
第三个示例:有很多可用的学生,派三名学生从第一堆中取出盒子,四名学生从第二堆中取出盒子,五名学生从第三堆中取出盒子,四名学生从第四堆中取出盒子。 5 秒后,当最后一堆盒子移走完毕后,整个过程就结束了。