题目描述

小P 是一位非常烦恼的教授，因为一路上有很多大堆的箱子挡住了他去学校的路。

总共有 $n$ 堆箱子，排列在一个直线上，从左到右编号为 $1$ 到 $n$，第 $i$ 堆有 $a_i$ 个箱子。幸运的是，有 $m$ 个学生愿意帮助 小P 清除他的路上的箱子。学生们同时工作。在时间 $0$ 时，所有学生都位于第一堆箱子的左侧。每个学生从这个位置移动到第一堆箱子需要 $1$ 秒钟，之后，每个学生都要执行两个可能的操作之一，每个操作需要 $1$ 秒钟。可能的操作有：

1. 如果 $i\neq n$，从第 $i$ 堆箱子移动到第 $i+1$ 堆箱子；
2. 如果学生所在位置上的堆不为空，则从中移除一个箱子。

小P 的学生们并不聪明，所以他们需要你告诉他们如何在教授到来之前（他是一个非常不耐烦的人，不想等待），将箱子全部清理掉。他们要求你计算最少需要多少秒的时间，才能将 小P 路上的所有箱子都清除掉。请注意，学生们在 $t$ 秒后可以按任意方式放置，但是所有的箱子必须被清除掉。

输入格式

第一行包含两个整数 $n$ 和 $m$，代表箱子的堆数和 小P 的学生数。

第二行包含 $n$ 个整数 $a_{1},a_{2},\ldots,a_{n}$，其中 $a_{i}$ 代表第 $i$ 堆箱子上的箱子数量。保证至少有一堆箱子不为空。

输出格式

在一行中输出一个数字，表示清除所有箱子所需的最少时间（以秒为单位）。

输入输出样例 #1

输入 #1

2 1
1 1

输出 #1

4

输入输出样例 #2

输入 #2

3 2
1 0 2

输出 #2

5

输入输出样例 #3

输入 #3

4 100
3 4 5 4

输出 #3

5

说明

数据范围

• 对于 $40\%$ 的数据, $0 \leq a_{i} \leq 1000, 1 \leq n,m \leq 100$。
• 对于 $60\%$ 的数据, $0 \leq a_{i} \leq 10^7, 1 \leq n,m \leq 10^4$。
• 对于 $100\%$ 的数据, $0 \leq a_{i} \leq 10^9, 1 \leq n,m \leq 10^5$。