Double Eleven Coupon Optimization

During the Double Eleven shopping festival, many customers are shopping crazily. A merchant offers a special promotion: there are \(n\) items with individual costs \(a_i\). You can choose to buy an item individually for its price or you can purchase a coupon for \(w\) that lets you redeem up to \(m\) items free of charge (with no extra cost per item). Even if the last coupon covers fewer than \(m\) items, it can still be used.

Determine the minimum total cost required to purchase all \(n\) items.

Approach: Sort the item prices in descending order. Then, partition the sorted list into groups of at most \(m\) items. For each group, the cost is the minimum between the sum of the group and the coupon price \(w\). Sum up these minimal costs for the answer.

inputFormat

The first line contains three integers \(n\), \(m\), and \(w\):

• \(1 \le n \le 10^5\)
• \(1 \le m \le n\)
• \(1 \le w, a_i \le 10^9\)

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the cost of each item.

outputFormat

Output a single integer representing the minimum total cost to purchase all \(n\) items.

sample

3 2 100
70 80 10

110