蓝春

题目描述

高桥计划进行一次 $N$ 天的火车旅行。

每一天,他可以选择支付普通票价,或者使用一日通票。

这里,对于 $1 \le i \le N$,旅行第 $i$ 天的普通票价为 $F_i$ 日元。

另一方面,一包 $D$ 张的一日通票以 $P$ 日元的价格出售。通票可以购买任意数量,但只能以 $D$ 张为单位购买。

每张购买的通票可以在任意一天使用,旅行结束后有剩余也没关系。

求这次 $N$ 天旅行的最小总费用,即购买一日通票的费用与未使用一日通票覆盖的天数的普通票价之和。

输入格式

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

$N$ $D$ $P$
$F_1$ $F_2$ $\dots$ $F_N$

输出格式

输出 $N$ 天旅行的最小总费用。

样例

5 2 10
7 1 6 3 6

20

如果他只购买一包一日通票,并在第 $1$ 天和第 $3$ 天使用,总费用为 $(10 \times 1)+(0+1+0+3+6)=20$,这就是所需的最小费用。

因此,输出 $20$。

3 1 10
1 2 3

6

全部三天都支付普通票价即可达到最小费用。

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

3000000000

购买三包一日通票并用于全部八天即可达到最小费用。

注意,答案可能超出 $32$ 位整数范围。

数据范围

• $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$
• 所有输入值均为整数。