分数: 300 点
问题陈述
有 N 商店里的物品。对于每个 i = 1, 2, \ldots, N,价格 i- 第一项是 A_i 日元(日本的货币)。
高桥有 K 优惠券。
每张优惠券可用于一件商品。您可以在同一商品上使用任意数量的优惠券(可能为零)。使用 k 商品的优惠券,价格为 a 日元可以让你购买它 \max\lbrace a - kX, 0\rbrace 日元。
打印高桥购买所有物品所需的最低金额。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K, X \leq 10^9
- 1 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K X A_1 A_2 \ldots A_N
输出
打印答案。
示例输入 1
5 4 7 8 3 10 5 13
示例输出 1
12
通过使用 1 优惠券 1-st 项目, 1 优惠券 3-rd 项目,以及 2 优惠券上 5第一项,高桥可以:
- 购买 1-st 项目 \max\lbrace A_1-X, 0 \rbrace = 1 日元,
- 购买 2-nd 项目 \max\lbrace A_2, 0 \rbrace = 3 日元,
- 购买 3-rd 项目 \max\lbrace A_3-X, 0 \rbrace = 3 日元,
- 购买 4- 第一项 \max\lbrace A_4, 0 \rbrace = 5 日元,
- 购买 5- 第一项 \max\lbrace A_5-2X, 0 \rbrace = 0 日元,
总共 1 + 3 + 3 + 5 + 0 = 12 日元,这是可能的最低金额。
示例输入 2
5 100 7 8 3 10 5 13
示例输出 2
0
示例输入 3
20 815 60 2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202
示例输出 3
112