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 a₁, a₂, …, a_n. a_i is the number of future billionaires in i-th month (0 ≤ a_i ≤ 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.