• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

Jeff is very indecisive. Whenever an opportunity arises, he rarely decides to pursue it. Each opportunity in Jeff’s life has two characteristics:

$1.$ $V$: the amount of happiness Jeff would gain if he chooses to take this opportunity.

$2.$ $W$: the amount of energy it would cost Jeff to take this opportunity.

Jeff has a limited amount of energy, $K$.

Over $Q$ moments in Jeff's life, opportunities either appear or disappear:

• In the i-th moment, an opportunity with values $V_i$​ (happiness) and $W_i$​ (energy cost) either becomes available or, if it was already available, disappears.

Now, at the end of his life, Jeff is filled with regrets. For each moment $1 \le i \le Q$, he wonders what the maximum happiness he could have achieved would have been if he had chosen to take some of the available opportunities, using no more than his available energy $K$.

Since Jeff doesn’t have the time to solve this problem himself, he’s asking for your help.

input

the first line contains two integers $Q$ and $K$, the number of moments in Jeff's life and the amount of energy Jeff has.

for the next $Q$ lines, the i-th line contains two integers each $V_i$ and $W_i$ the amount of happiness and the energy cost of the opportunity.

if Jeff previously had the opportunity with the same values the opportunity is no longer available otherwise the opportunity becomes available.

$$1 \le Q \le 2500$$ $$0 \le K \le 2500$$ $$0 \le V_i \le 2500$$$$1 \le W_i \le 2500$$

output

output should contain $Q$ numbers the i-th number should be the maximum amount of happiness Jeff could've achieved if he had chosen to take some of the available opportunities at the i-th moment such that the amount of energy he loses is at most $K$.

example

sample input 1

8 7
4 4
9 2
9 2
7 6
7 6
2 7
4 4
7 4

sample output 1

4
13
4
7
4
4
2
7

• in moment 1 available opportunities are $[(4, 4)]$ Jeff can take opportunity $1$ and gain $4$ happiness
• in moment 2 available opportunities are $[(4, 4), (9, 2)]$ Jeff can take opportunities $1, 2$ and gain $9+4=13$ happiness
• in moment 3 opportunity $(9, 2)$ disappears so opportunities are $[(4, 4)]$ Jeff can take opportunity $1$ and gain $4$ happiness
• in moment 4 available opportunities are $[(4, 4), (7, 6)]$ Jeff can take opportunity $2$ and gain $7$ happiness, he can't take both opportunities since his available energy $K$ is equal to $7$ but taking both opportunities would require energy of at least $7+4=13$