# Algorithms – How to use a radiator to dry rags as efficiently as possible, knowing that each rag dries water in a minute?

Warning

This is not an ongoing contest, this is my ITMO course on edx.org. I can not give the direct link to the problem as it is a paid course.

description of the problem

It is very difficult to wash and especially to dry clothes in winter. But Jane is a very smart girl. She is not afraid of this boring process. Jane decided to use a radiator to speed up drying. But since the radiator is small, it can only contain one thing at a time.

Jane wants to dry as quickly as possible. She asked you to write a program calculating the minimum time for a given set of clothes.

There is $$displaystyle n$$ clothes that Jane just washed. Each of them took $$displaystyle a_i$$ water during washing. Every minute, the amount of water contained in each thing decreases by one unit (of course, only if the thing is not yet completely dry). When the amount of water contained becomes zero, the cloth becomes dry and is ready to be packaged.

Every minute, Jane can choose something to dry on the radiator. The radiator is very hot, so the amount of water in this thing decreases by this minute (but not less than zero – if the thing contains less than $$displaystyle k$$ water, the resulting amount of water will be zero).

The task is to minimize the total drying time by effectively using the radiator. The drying process ends when all the clothes are dry.

Contribution

The first line contains a single integer $$displaystyle n$$ ($$displaystyle 1 <= n$$ <= $$10 ^ {5}$$). The second line contains $$displaystyle a_i$$ ($$displaystyle 1 <= a_i$$ <= $$10 ^ {9}$$) separated by spaces. The third line contains k ($$displaystyle 1 <= k$$ <= $$10 ^ {9}$$).

Exit

Display a single integer – the minimum number of minutes to dry all clothes.

Example 1

``````contribution
3
2 3 9
5

exit
3
``````

Example 2

``````contribution
3
2 3 6
5
exit
2
``````

I can not understand how they can use the radiator so effectively, not to mention writing the corresponding code.