#ABC318C. 青春
青春
AT_abc318_c [ABC318C] Blue Spring
题目描述
高桥君要进行 天的旅行,第 天的费用为 。
他还可以购买优惠券,一张优惠券的价格为 ,可以免除 天的费用。如果剩余的天数不足 天,这张优惠券依然可以使用。
求这 天旅行的最小费用。
输入格式
第一行输入三个整数 $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)$ 代表旅行的天数、一张优惠券可以免除的天数和一张优惠券的价格。
第二行输入 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right)$,其中 代表第 天的费用。
输出格式
在一行上输出一个整数,代表这 天旅行的最小费用。
测试样例
5 2 10
7 1 6 3 6
20
样例 1 解释
使用一张优惠券免除第 天和第 天的费用,这两天的费用分别为 和 ;其余第 天的费用 直接支付,再加上优惠券的价格 ,总费用为 。
3 1 10
1 2 3
6
8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
3000000000
样例 3 解释
使用 张优惠券即可覆盖全部 天,总费用为 。