ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1648. Яхты

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

Исходные данные

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

Результат

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

Пример

исходные данныерезультат
3 5
6 1 7
13 2
Автор задачи: Алексей Самсонов
Источник задачи: Осеннее первенство школьников 2008