题目描述

国家储备林建设纳入国家规划。在工程实施过程中，某地区计划建设 $n$ 个生态林区，每个林区的预计耗水定额为 $p_i$。

为了优化资源配置，水利部门提供了两种水资源补偿方案。企业可以将这 $n$ 个林区划分为若干个批次进行建设（每个林区必须且只能属于一个批次，分组不要求保持原有顺序）：

1. 分步建设模式：如果一个批次中包含的林区数量少于 $k$ 个，则该批次内的每个林区均可获得 $d$ 单位的资源补贴（即该林区的实际耗水定额为 $\max(0, p_i - d)$）。
2. 集约建设模式：如果一个批次中恰好包含 $k$ 个林区，则该批次中耗水定额最低的一个林区完全免费（实际耗水为 $0$），而该批次内的其余 $k-1$ 个林区必须按原定额 $p_i$ 消耗，不再享受 $d$ 单位的定额补贴。

根据规定，每个批次最多只能包含 $k$ 个林区。

作为工程负责人，请你制定最优的分批建设方案，使得完成所有 $n$ 个林区建设所需的总耗水定额最小。

输入格式

第一行包含三个整数 $n, k, d$，分别表示林区的数量、集约模式的门槛数量、以及分步建设模式的定额补贴。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，表示每个林区的原始耗水定额。

输出格式

输出一个整数，表示完成建设所需的最小总耗水定额。

5 3 20
10 20 30 40 50

60

提示

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1 \le n \le 1000$，$2 \le k \le 10$。

对于所有的评测用例，$1 \le n \le 2 \times 10^5$，$2 \le k \le n$，$0 \le d \le 10^9$，$1 \le p_i \le 10^9$。