当前没有测试数据。

AIO 2026 - 第 3 题：Discount Destinations

题目 3：优惠出行

时间限制： 1 秒 内存限制： 256 MB

你从繁忙的日程中腾出了连续 (N) 天去旅行！

而且，你决定依赖你所在州一贯“可靠”的公共交通前往各个目的地。

第 (i) 天的行程，原本通常需要花费 $(A_i)$美元。

不过，最近由于人们对生活成本的抱怨，政府推出了一项新的优惠制度：

对于任意连续的 (K) 天，你的总支出最多只能是 (D) 美元。

这些天会按照第 (1) 天到第 (N) 天的顺序依次处理。

在第 (i) 天，你实际被收取的费用，是一个不超过 (A_i) 的最大非负整数，并且要求在收取这笔费用之后：

最近连续 (K) 天内的总收费不超过 (D)。

你可以认为：

在第 1 天之前的所有天，你都没有被收取任何费用。

现在有了这个新制度，你需要计算：

这次假期中，乘坐公共交通一共需要花多少钱？

---

子任务与限制

你的程序会使用许多隐藏测试数据进行评测。

所有测试数据均满足：

• $(2 \le N \le 200000)$
• $(1 \le K \le N)$
• $(1 \le D \le 10000)$
• 对于所有 (i)：

$$1 \le A_i \le 10000$$

隐藏测试被划分成若干子任务。

你的程序必须正确通过某个子任务中的全部测试，才能获得该子任务的分数。

• 子任务 1（20 分）：(K=1)
• 子任务 2（10 分）：对于所有 (i)，(A_i=1)
• 子任务 3（35 分）：(N,K\le1000)
• 子任务 4（35 分）：无额外限制

---

输入

你的程序需要读取输入并输出结果。

官方建议使用比赛网站提供的代码模板来帮助处理输入输出。

输入格式如下：

• 第一行包含三个整数：

$$N,\ K,\ D$$

• 第二行包含 (N) 个整数：

$$A_1,A_2,\ldots,A_N$$

其中 (A_i) 表示第 (i) 天在没有任何优惠时原本需要支付的金额。

---

输出

你的程序需要输出：

在这 (N) 天中，你实际一共需要支付的美元总额。

---

样例输入 1

5 1 3
2 4 7 1 3

样例输出 1

12

---

样例输入 2

5 3 3
1 2 3 2 1

样例输出 2

5

---

样例输入 3

5 5 9
1 2 3 4 5

样例输出 3

9

---

样例说明

样例 1

这里：

$$K=1,\ D=3$$

也就是说：

每一天的支出都不能超过 3 美元。

原价与实际支付金额如下：

天数	原价	实际支付
1	$2
2	$4	$3
3	$7
4	$1
5	$3

所以总花费为：

$$2+3+3+1+3=12$$

---

样例 2

这里：

$$K=3,\ D=3$$

也就是说：

任意连续 3 天内，总支出最多为 3 美元。

原价：

1 2 3 2 1

实际支付：

1 2 0 1 1

验证：

第 1～3 天：

$$1+2+0=3$$

第 2～4 天：

$$2+0+1=3$$

第 3～5 天：

$$0+1+1=2$$

都没有超过 (3)。

因此总花费：

$$1+2+0+1+1=5$$

---

样例 3

这里：

$$N=5,\ K=5,\ D=9$$

原价：

1 2 3 4 5

因为任意连续 5 天实际上就是全部 5 天，所以总支付不能超过：

$$9$$

最终一共支付：

9

美元。