問題文

「旅行に行くとき，荷物はコンパクトにまとめる必要がありますね」

にぼしくんには$N$個の荷物があります．$i$番目の荷物の価値は$v_i$で重さは$w_i$です．また，容量が$W$のカバンを$1$つ持っています．
明日からの旅行に備えてにぼしくんは荷造りをしなければなりませんが， 優柔不断なにぼしくんは何を持っていくかまだ決められないようです．

荷物を全部詰め込めるならそうしたいですが，現実はそううまくいくとは限りません．

そこでにぼしくんは考えました．
「これを置いていったらこれを持っていけるかも...」

以下の問いに$N$回答えてください． 問$i$の形式は以下の通りです．

• 問$i:$ 重さの総和が$W$以下であって，選ばれた荷物の集合に$i$番目の荷物を含まないものの価値の総和の最大値

制約

• $2 \leq N \leq 10^3$
• $1 \leq W \leq 10^3$
• $0 \leq v_i \leq 10^9$
• $1 \leq w_i \leq 10^3$
• 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられます．

出力

答えを$N$行に出力せよ．$i$行目には問$i$の答えを出力せよ．

サンプル

4 10
50 3
70 4
80 6
40 4

150
130
120
150

• $1$番目の荷物を含まないものの荷物の集合として$2$番目と$3$番目の荷物を選ぶと価値の総和は$70+80=150$で重さの総和は$4+6=10$となります．
• $2$番目の荷物を含まないものの荷物の集合として$1$番目と$3$番目の荷物を選ぶと価値の総和は$50+80=130$で重さの総和は$3+6=9$となります．
• $3$番目の荷物を含まないものの荷物の集合として$1$番目と$2$番目の荷物を選ぶと価値の総和は$50+70=120$で重さの総和は$4+6=10$となります．
• $4$番目の荷物を含まないものの荷物の集合として$2$番目と$3$番目の荷物を選ぶと価値の総和は$70+80=150$で重さの総和は$4+6=10$となります．

10 1000
775501458 530
362833899 622
552902855 55
758447415 280
481627741 689
797601219 320
746924356 667
300648492 83
906611809 100
539171652 552

3316211790
3316211790
2763308935
2557764375
3316211790
2993463537
3316211790
3015563298
2426654024
3316211790