Problem Description

The construction of national reserve forests has been included in the national plan. During the project implementation, a certain region plans to build $n$ ecological forest areas, and the expected water-use quota of the $i$-th area is $p_i$.

To optimize resource allocation, the water resources department provides two compensation plans. The company can divide these $n$ forest areas into several batches for construction (each forest area must belong to exactly one batch, and the grouping does not need to keep the original order):

1. Step-by-step construction mode: If a batch contains fewer than $k$ forest areas, then each forest area in this batch can receive a subsidy of $d$ units of resources (that is, its actual water-use quota is $\max(0, p_i - d)$).
2. Intensive construction mode: If a batch contains exactly $k$ forest areas, then the forest area with the smallest water-use quota in this batch is completely free (its actual water use is $0$), while the other $k-1$ forest areas in this batch must consume according to the original quotas $p_i$ and no longer enjoy the $d$-unit quota subsidy.

According to the rules, each batch can contain at most $k$ forest areas.

As the project leader, please design an optimal batching plan so that the total water-use quota required to complete the construction of all $n$ forest areas is minimized.

Input Format

The first line contains three integers $n, k, d$, representing the number of forest areas, the threshold size for the intensive mode, and the quota subsidy for the step-by-step mode.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$, representing the original water-use quotas of each forest area.

Output Format

Output one integer, representing the minimum total water-use quota required to complete the construction.

5 3 20
10 20 30 40 50

60

Hint

[Test Case Scale and Assumptions]

For $30\%$ of the test cases, $1 \le n \le 1000$, $2 \le k \le 10$.

For all test cases, $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$.

Translated by ChatGPT 5