P16819 [Lanquiao Cup 2026 National Python B] Minimum Water-Use Quota

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.

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 one integer, representing the minimum total water-use quota required to complete the construction.

### [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