F. Banners
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
stdin
вывод
stdout

Все современные мобильные приложения делятся на платные и бесплатные. Даже разработчики одного приложения часто выпускают две версии: платную версию без рекламы и бесплатную версию с рекламой.

Предположим, что платная версия приложения стоит 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