Knapsack Expect i-th

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

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

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

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

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

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

• 入力される値はすべて整数である

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

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

4 10
50 3
70 4
80 6
40 4

150
130
120
150

• 番目の荷物を含まないものの荷物の集合として番目と番目の荷物を選ぶと価値の総和はで重さの総和はとなります．
• 番目の荷物を含まないものの荷物の集合として番目と番目の荷物を選ぶと価値の総和はで重さの総和はとなります．
• 番目の荷物を含まないものの荷物の集合として番目と番目の荷物を選ぶと価値の総和はで重さの総和はとなります．
• 番目の荷物を含まないものの荷物の集合として番目と番目の荷物を選ぶと価値の総和はで重さの総和はとなります．

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