P2094 Transportation

There are $N$ goods, and the handling fee for each of them is known. The moving company boss, Mr. sb, decides that each time we can arbitrarily pick $2$ goods. Then these $2$ goods count as only one item’s fee, where the new item’s handling fee is the result of dividing the sum of the two selected items’ fees by $k$. Repeat this process until only one item’s fee remains. This final amount is what the shop has to pay. The shopkeeper wants to pay as little as possible so that more money can be donated to Project Hope (Xiwang Gongcheng). Please help compute the minimum amount that needs to be paid.

The first line contains two integers $n, k$. The second line contains $n$ integers $w_1, w_2, \ldots, w_n$, representing the handling fee of each item.

Output a single integer, the minimum amount that needs to be paid.

$n, k, w_i$ are all non-negative. $n, k \le 10^4$. --- $\text{upd 2022.7.24}$: Added one set of Hack testdata. Whether there exists a correct solution within this constraint range is controversial. Translated by ChatGPT 5