← 返回题目列表

AtCoder · abc246_c

F. 优惠券

中文机器翻译题面 查看原题

分数: 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