题目描述

强哥决定资助一批贫困学生完成 $N$ 天的暑期学习营。 第 $i$ 天的学习材料费用为 $A_i$ 元。

为了帮助更多孩子，某慈善机构推出了一种“爱心助学券”，每张价格为 $P$ 元，使用后可以免除 $D$ 天的学习材料费用（不一定要连续的$D$天）。 特别说明：如果剩余天数不足 $D$ 天，只要还有学生需要帮助，依然可以使用助学券（例如剩余 $2$ 天时，券上写着“可免 $3$ 天费用”，依然有效）。

强哥希望用最少的钱帮助所有学生完成学习营，请你帮他计算最小总费用。

输入格式

第一行包含 $3$ 个整数：$N, D, P$，分别表示学习营天数、每张助学券可免除的天数、每张助学券的价格。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示每天的学习材料费用。

输出格式

输出一个整数，表示强哥需要支付的最小总费用。

输入输出样例

样例 1

输入

5 2 10
7 1 6 3 6

输出

20

样例 2

输入

3 1 10
1 2 3

输出

6

样例 3

输入

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

输出

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 A_i \le 10^9$