Transportation

Problem Description

Now we know there are $N$ items, and the cost to move each one individually. The moving company's boss, Mr. S, decides that each time we may arbitrarily pick $2$ items. Then these $2$ items are charged as only one item. But the moving cost for these $2$ items is the result of dividing the sum of the two items' costs by $k$. Repeat this until only one item's worth of money is charged. This is the fee the store has to pay. The shopkeeper wants to pay as little as possible, so as to donate more money to the Hope Project. Please help him compute the minimum amount he has to pay.

Input Format

The first line contains two integers $n, k$.

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$, the moving cost of each item.

Output Format

One line with a single integer, the minimum amount to pay.

Sample Input

5 2
1 2 3 4 5

Sample Output

1

Hint

$n, k, w_i$ are all non-negative numbers. $n, k \le 10^4$.

$\text{upd 2022.7.24}$: A new Hack test case was added. Whether a correct solution exists for this data range is disputed.