Description

小明计划进行为期 $N$ 天的火车旅行。每一天，他可以选择支付常规票价，或者使用一日通票。

• 第 $i$ 天的常规票价为 $F_i$ 元。
• 一批 $D$ 张的一日通票售价为 $P$ 元。你可以购买任意数量的一日通票，但只能以 $D$ 张为单位购买。每张一日通票可以在任何一天使用，即使在旅程结束时有未使用的通票也没有关系。

小明希望找到这次 $N$ 天旅行的最低总费用，即购买一日通票的费用加上未使用通票的天数的常规票价之和。

请帮小明计算出这次旅行的最小可能花费。

Format

Input

N D P
F_1
F_2
…
F_N

第一行包含三个整数 $N$、$D$ 和 $P$，分别表示旅行的天数、每批一日通票的数量和每批通票的价格。

接下来的 $N$ 行分别包含整数 $F_i$，表示第 $i$ 天的常规票价。

Output

输出一个整数，表示这次旅行的最低总费用。

Samples

样例输入 1

5 2 10
7
1
6
3
6

样例输出 1

20

解释

小明可以购买一批两张一日通票，并在第 1 天和第 3 天使用它们。其余的天数支付常规票价，因此总费用为：

(10 × 1) + (0 + 1 + 0 + 3 + 6) = 20

样例输入 2

3 1 10
1
2
3

样例输出 2

6

解释

最小费用是支付每一天的常规票价，不购买一日通票，总费用为：

1 + 2 + 3 = 6

样例输入 3

8 3 1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000

样例输出 3

3000000000

解释

小明可以购买三批通票，并在所有 8 天内使用通票，最小总费用为：

3 × 1000000000 = 3000000000

Limitation

1000ms 256MB

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq D \leq 2 \times 10^5$
• $1 \leq P \leq 10^9$
• $1 \leq F_i \leq 10^9$
• 所有输入的值均为整数。