#ABC318C. 青春

青春

AT_abc318_c [ABC318C] Blue Spring

题目描述

\hspace{15pt}高桥君要进行 nn 天的旅行,第 ii 天的费用为 aia_i。

\hspace{15pt}他还可以购买优惠券,一张优惠券的价格为 pp,可以免除 dd 天的费用。如果剩余的天数不足 dd 天,这张优惠券依然可以使用。

\hspace{15pt}求这 nn 天旅行的最小费用。

输入格式

\hspace{15pt}第一行输入三个整数 $n, d, p \left(1 \leqq n \leqq 2 \times 10^5;\ 1 \leqq d \leqq 2 \times 10^5;\ 1 \leqq p \leqq 10^9\right)$ 代表旅行的天数、一张优惠券可以免除的天数和一张优惠券的价格。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right)$,其中 aia_i 代表第 ii 天的费用。

输出格式

\hspace{15pt}在一行上输出一个整数,代表这 nn 天旅行的最小费用。

测试样例

5 2 10
7 1 6 3 6
20

样例 1 解释

\hspace{15pt}使用一张优惠券免除第 11 天和第 33 天的费用,这两天的费用分别为 77 和 66;其余第 2,4,52,4,5 天的费用 1,3,61, 3, 6 直接支付,再加上优惠券的价格 1010,总费用为 1+3+6+10=201+3+6+10=20。

3 1 10
1 2 3
6
8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
3000000000

样例 3 解释

\hspace{15pt}使用 33 张优惠券即可覆盖全部 88 天,总费用为 3×1093 \times 10^9。