Всем известно, что лучшие в мире яхты строит знаменитая Екатеринозаводская верфь. Они настолько популярны, что как только богатый промышленник становится миллиардером, он в конце того же месяца приходит на верфь за яхтой. Ещё бы! На Екатеринозаводской верфи яхты изготавливаются вручную, в оформлении интерьера используются ценные породы красно-чёрного дерева… К сожалению, на верфи совсем немного рабочих, поэтому за месяц она может построить не более d новых яхт. В результате, верфь не всегда успевает справиться с наплывом покупателей. А миллиардеры — люди гордые: если они придут на верфь, а готовой яхты там не будет, то они обидятся и раздумают совершать покупку. Конечно, верфь может производить яхты впрок, но хранение готовых яхт недёшево — один месяц хранения одной яхты обходится верфи в 1 золотой слиток.

Руководство решило узнать, какое максимальное количество яхт сможет продать верфь в ближайшие n месяцев и какое минимальное количество золота для этого придётся потратить на хранение готовых яхт. С этой целью руководство обратилось к студентам экономического факультета Екатеринозаводского университета, и те, исследовав динамику роста цен на полезные ископаемые, посчитали, сколько людей станет миллиардерами в каждый из n ближайших месяцев. Ваша же цель — ответить на вопросы руководства, используя эту информацию.

В первой строке через пробел записаны целые числа n и d (1 ≤ n ≤ 20000; 1 ≤ d ≤ 100000). Во второй строке через пробел записаны целые числа a₁, a₂, …, a_n. Число a_i обозначает количество людей, которые станут миллиардерами в i-й месяц (0 ≤ a_i ≤ 100000).

Выведите через пробел два числа — максимальное количество яхт, которое сможет продать верфь, и минимальное количество золотых слитков, которое для этого придётся потратить на хранение готовых яхт.