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$ 位整数可以表示的范围。