← 返回题目列表

Codeforces · 551/C

C. GukiZ 讨厌盒子

中文机器翻译题面 查看原题

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 秒后,当最后一堆盒子移走完毕后,整个过程就结束了。