409744: GYM103715 E Магические зелья

E. Магические зельяограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Саша играет в новую MMORPG игру. В этой игре вся сила персонажа зависит от единственного параметра — удачи. Удача измеряется целым числом. Сейчас у персонажа Саши параметр удачи равен $$$k$$$.

В игре есть зелья, которые могут изменять удачу как в большую, так и в меньшую сторону. Существуют зелья двух типов:

1) Зелье первого типа устанавливает параметр удачи у персонажа равным $$$x$$$. Формально, если перед использованием этого зелья удача была $$$k$$$, то после его использование удача станет равна $$$x$$$.

2) Зелье второго типа изменяет параметр удачи у персонажа на $$$x$$$ единиц. Формально, если перед использованием этого зелья удача была $$$k$$$, то после его использование удача станет равна $$$k + x$$$.

У Саши есть всего $$$n$$$ волшебных зелий и при помощи них Саша хочет сделать своего персонажа как можно сильнее. Саша может использовать зелья в любом порядке.

Саша ещё не решил сколько зелий он хочет использовать и поэтому он просит вас для каждого $$$i$$$ ($$$1 \le i \le n$$$) найти максимальную удачу персонажа, если он использует $$$i$$$ зелий.

Входные данные

Первая строка входных данных содержит два числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^5, -10^9 \le k \le 10^9$$$) — количество зелий у Саши и изначальный параметр удачи у персонажа.

Следующие $$$n$$$ строк входных данных описывают зелья. Каждая строка содержит два числа $$$t$$$ и $$$x$$$ ($$$1 \le t \le 2, -10^9 \le x \le 10^9$$$) — тип зелья и параметр $$$x$$$ у зелья.

Выходные данные

Выведите $$$n$$$ чисел через пробел: $$$i$$$-е число выходных данных должно быть равно максимальной удаче после использования $$$i$$$ зелий.

ПримерыВходные данные

4 5
1 10
2 10
2 -5
1 -1

Выходные данные

15 20 20 20 

Входные данные

3 -1
2 -1
2 -1
2 -1

Выходные данные

-2 -3 -4 

Входные данные

3 7
1 10
2 -5
2 -3

Выходные данные

10 10 10 

Примечание

В первом примере изначальный параметр удачи у персонажа равен $$$5$$$.

Если использовать одно зелье, то максимальная удача достигается при использовании второго зелья: $$$5 + 10 = 15$$$.

Если использовать два зелья, то для получения максимальной удачи, нужно сначала использовать первое зелье и получить удачу $$$10$$$, а после — второе зелье и получить удачу $$$10 + 10 = 20$$$.

Если использовать три зелья, то для получения максимальной удачи, нужно использовать зелья в следующем порядке: $$$4, 1, 2$$$. В таком случае, сначала показатель удачи станет равным $$$-1$$$, затем $$$10$$$ и поле третьего зелья $$$20$$$. В данном случае, можно вместо зелья №4 использовать зельe №3, но максимальный результат после трех зелий, все равно будет равен $$$20$$$.

Если использовать четыре зелья, то для получения максимальной удачи, нужно использовать зелья в следующем порядке: $$$3, 4, 1, 2$$$ и получить удачу равную $$$20$$$.

Во втором примере все зелья уменьшают текущую удачу на $$$1$$$, поэтому каждый следующий ответ на $$$1$$$ меньше чем предыдущий.

В третьем примере всегда выгодно использовать зелье №1 последним и тогда показатель удачи будет равен $$$10$$$.