ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Autumn school contest 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Yachts

Time limit: 1.0 second
Memory limit: 64 MB
Everybody knows that the Yekaterinozavodsk Shipyard constructs the best yachts in the world. They are so popular that when a manufacturer becomes a billionaire, he comes to the shipyard in the end of the same month to get a new yacht. You bet! The yachts are hand-made and their interior is made from a valuable red-black tree. Unfortunately, there are few workers at the shipyard, therefore, it can build no more than d new yachts per month. As a result, the shipyard sometimes cannot produce enough yachts for their customers. And those billionaires are quite impulsive people: if they come to the shipyard and there is no yacht for them, they abandon the whole idea of buying a yacht. Of course, the shipyard can produce yachts and store them somewhere for future use, but you should pay 1 golden bar to store one yacht during one month.
The managers want to know the maximal number of yachts the shipyard can sell during the next n months, and the miminal number of golden bars which should be paid for the storage. The students from the Department of Economics of the Yekaterinozavodsk University predicted the amount of future billionaires in each of these n months. You should use this data to answer the managers' questions.


The first line contain space-separated integers n and d (1 ≤ n ≤ 20000; 1 ≤ d ≤ 100000). The second line contains space-separated integers a1, a2, …, an. ai is the number of future billionaires in i-th month (0 ≤ ai ≤ 100000).


Output two integers separated by space — the maximal number of yachts the shipyard can sell and the minimal number of golden bars required to pay for the storage.


3 5
6 1 7
13 2
Problem Author: Alexey Samsonov
Problem Source: USU Junior Contest, October 2008
To submit the solution for this problem go to the Problem set: 1648. Yachts