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