Dmytro and Bottles#10249
Dmytro has plastic bottles, each capable of holding exactly liters of water. The -th bottle currently contains a_i liters of water.
Having recently become aware of the environmental impact of plastic, Dmytro wants to recycle as many bottles as possible. To achieve this, he plans to redistribute the water among the bottles so that no bottle exceeds its capacity of liters. However, Dmytro prefers to minimize the amount of water he has to pour.
Your task is to help Dmytro determine the minimum number of bottles required to hold all the water and the minimum number of liters that need to be poured.
Note that water from one bottle can be distributed across multiple other bottles. It is not necessary to transfer all the water from one bottle into just one other bottle.
The first line contains two integers and (1 \leq n \leq 10^5, 1 \leq k \leq 10^4) — the number of bottles and the maximum capacity of each bottle.
The second line contains integers a_1, a_2, \ldots, a_n (0 \leq a_i \leq k) — the current amount of water in each bottle.
Output a single line with two integers: the number of bottles needed to hold all the water, and the minimum number of liters that need to be poured.
Example 1
Example 2
Example 3
In the first example, all the water from the th bottle can be transferred to the rd bottle, and the water from the st bottle can be poured into the th bottle.
In the second example, all 5 bottles are required, so no pouring is necessary.
In the third example, you can select any bottle and pour 1 liter from it into all the others.