You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

T5 Blue Spring

题目描述

小z正在计划一场为期$N$天的铁路旅行。
对于每一天，小z可以选择支付正常票价，或者使用一张一日通票。

这里，对于$1\leq i\leq N$，第$i$天旅行的正常票价为$F_i$元。
另一方面，一日通票以$D$张为一套，售价$P$元，可以购买任意套数，但只能以$D$张为单位购买。
此外，购买的通票可以在任意一天使用一张，旅行结束时即使有剩余也没关系。

请计算$N$天旅行可能花费的最小金额，即购买一日通票的费用与未使用一日通票当天正常票价总和的最小值。

输入格式

第一行有 $3$ 个整数 $N,D,P$。

第二行有 $N$ 个整数，第 $i$ 个为 $A_i$。

输出格式

$1$ 个整数，如题意。

样例 #1

样例输入 #1

5 2 10
7 1 6 3 6

样例输出 #1

20

样例 #2

样例输入 #2

3 1 10
1 2 3

样例输出 #2

6

样例 #3

样例输入 #3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

样例输出 #3

3000000000

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le D \le 2 \times 10^5$
• $1 \le P \le 10^9$
• $1 \le F_i \le 10^9$

样例一解释

只购买1套一日周游券，并在第1天和第3天使用，那么总金额为$(10×1)+(0 + 1 + 0 + 3 + 6)=20$，此时花费的金额最小。 因此，输出20。

样例三解释

购买3套一日周游券，在全部8天里都使用一日周游券时花费最小。

请注意，答案有可能无法用32位整数类型表示。