Все современные мобильные приложения делятся на платные и бесплатные. Даже разработчики одного приложения часто выпускают две версии: платную версию без рекламы и бесплатную версию с рекламой.
Предположим, что платная версия приложения стоит p (p — целое число) рублей, а бесплатная версия приложения содержит c рекламных баннеров. Каждого пользователя можно охарактеризовать двумя целыми числами: ai — сколько рублей этот пользователь не пожалеет за платную версию приложения, и bi — сколько баннеров он готов терпеть в бесплатной версии приложения.
Поведение каждого пользователя будем считать строго детерминированным:
- если для пользователя i значение bi не меньше c, тогда он пользуется бесплатной версией,
- иначе, если значение ai не меньше p, то он покупает платную версию без рекламы,
- иначе пользователь просто не пользуется приложением.
Каждый пользователь бесплатной версии приложения приносит прибыль c × w рублей. Каждый пользователь платной версии приложения приносит прибыль p рублей.
Ваша задача — помочь разработчикам приложения оптимально выбрать параметры p и c. А именно, считая, что известны все характеристики пользователей, для каждого значения c от 0 до (max bi) + 1 определить максимальную прибыль от приложения и соответствующий параметр p.
Выходные данные
Выведите (max bi) + 2 строки, в i-й строке выведите два целых числа: pay — максимальная полученная прибыль при c = i - 1, p (0 ≤ p ≤ 109) — соответствующая оптимальная стоимость. Если существует несколько оптимальных решений, разрешается вывести любое.