Problem 7C. 分发物资

题目描述

现在数轴的 \(1,2\cdots ,n\) 处各有一个人，他们各需要 \(a_1,a_2,\cdots ,a_n\) 的物资。

因此，你准备了 \(m=\sum_{i=1}^n a_i\) 份物资准备分发。

给定参数 \(k\)，你可以进行以下操作：

• 花费 \(1\) 的时间，选择一段区间 \([l, r]\)，且满足\(1\le l\le r\le n\) 和 \(r-l+1\le k\)， 并且你的剩余物资数至少要有 \(r-l+1\) 份 。接下来，向数轴上位置为 \(l,l+1,\cdots ,r\) 的人各分发一份物资。

求至少需要多少时间，才能满足所有人的需求。

输入格式

第一行两个整数 \(n,k\)，表示需要分发的人数和每次最多分发的人数。

第二行 \(n\) 个整数 \(a_i\)，表示每个人需要物资的份数。

输出格式

仅一个整数，表示至少需要的时间。

样例输入1

4 2
1 4 2 1

样例输出1

5

样例1解释

每次至多分发给连续的两个人。

操作如下：

1 1 0 0

1 2 2 0

1 3 2 0

1 4 2 0

1 4 2 1

样例输入2

7 4
1 5 2 4 2 4 2

样例输出2

9

数据范围与约定

对于 \(40\%\) 的数据，\(n=k=2\)。

对于另外 \(20 \%\) 的数据，\(k=n\)。

对于另外 \(20\%\) 的数据，\(1\le n,a_i\le 100\)。

以上三部分数据不重合，占本题 \(80\%\) 的分数。

对于 \(100\%\) 的数据，\(1\le k\le n\le 5\times 10^5\)，\(1\le a_i\le 10^9\)

注意，答案可能超过 \(32\) 位整数可以表示的范围。