AT_abc246_c [ABC246C] Coupon

题目描述

有 $N$ 个商品。对于 $i=1,2,\ldots,N$，第 $i$ 个商品的价格为 $A_i$ 日元。

高桥君有 $K$ 张优惠券。
每张优惠券可以用于一个商品，每个商品可以使用任意数量的优惠券（可以为 $0$ 张）。如果对价格为 $a$ 日元的商品使用 $k$ 张优惠券，则该商品可以以 $\max\lbrace a-kX,\,0\rbrace$ 日元的价格购买。

请输出高桥君购买所有商品所需支付的最小总金额。

输入格式

输入以以下格式从标准输入中给出。

$N$ $K$ $X$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

5 4 7
8 3 10 5 13

输出 #1

12

输入输出样例 #2

输入 #2

5 100 7
8 3 10 5 13

输出 #2

0

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K, X \leq 10^9$
• $1 \leq A_i \leq 10^9$
• 所有输入均为整数

样例解释 1

如果对第 $1$ 个商品使用 $1$ 张优惠券，对第 $3$ 个商品使用 $1$ 张优惠券，对第 $5$ 个商品使用 $2$ 张优惠券，则

• 第 $1$ 个商品可以以 $\max\lbrace A_1-X,\,0\rbrace=1$ 日元购买，
• 第 $2$ 个商品可以以 $\max\lbrace A_2,\,0\rbrace=3$ 日元购买，
• 第 $3$ 个商品可以以 $\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$ 日元购买，这是最小值。

由 ChatGPT 4.1 翻译