問題文
E869120君は、3年後、見事にコンテストのwriterをすることになった。- E869120君の問題ストックは$N$問ある。
- $i$個目の問題を投稿することによって、$v_i$【円】がもらえる。
- $i$個目の問題を投稿する作業にかかる時間は$w_i$【単位時間】である。
そこで、E869120君がもらえるお金を最大化し、その値を出力しなさい。ただし、問題は何問でも投稿できるものとし、問題の対象となっているコンテスト（コンテストサイトではない）のwriterは全てE869120君と仮定して良いので、投稿した問題は全てコンテストに出されることも保証される。
制約
- 1≦$N$≦48
- 1≦$W$, $v_i$, $w_i$≦1 000 000 000 000 000
小課題
- 1≦N≦20を満たすデータセットに正解した場合、25点が与えられる。
- 1≦N≦40を満たすデータセットに正解した場合、25点が与えられる。
- 1≦N≦42を満たすデータセットに正解した場合、10点が与えられる。
- 1≦N≦44を満たすデータセットに正解した場合、10点が与えられる。
- 1≦N≦46を満たすデータセットに正解した場合、15点が与えられる。
- 1≦N≦48を満たすデータセットに正解した場合、15点が与えられる。
- 合計100点である。
入力
N W v[1] w[1] v[2] w[2] ：：：： v[N] w[N]
入力例1
4 5 4 2 5 2 2 1 8 3
出力例1
13
入力例2
2 20 5 9 4 10
出力例2
9
入力例3
3 100 1 1 10 10 12 100
出力例3
12
入力例4
48 942383900389538 233051565987597 8392854223533 742662700939242 18342942502284 514343362113742 25179427037502 51720105724240 36613275934215 323857179457749 32357267699855 264752903453705 45079864932128 84958291201735 48681930378584 845908321040547 36903875515074 382307237577450 36785512343350 531544848502288 54640549401792 707114780707716 8031873709286 662053928254059 19883112675872 900089869128226 32155657542039 510730359513751 32741742035457 89171685118820 55611882637115 142882603602331 41407851979545 244611093482110 4862823666513 860637199907825 21356544587809 648105506530705 12558920837315 68936163210047 42996424598705 240879817488595 28253097079939 155504812695922 704376483486 284737072040707 20716982213071 756215289984873 23669379256697 785237535925689 42686586141619 389785308959357 663000264933 929251979499963 61196702235443 637705779671560 6446529060034 677277645922992 47468341986547 143871998910106 27613843131065 93025949293580 21723904323138 920015409483820 34996073533825 565114754634746 10052619423442 568966630572845 49305148386369 28496305483803 31316251835364 422227040430040 59204945107756 64727950078985 32994543765951 857244478252721 14749999986568 43040196015068 42817660840027 366691024238478 61714620273807 315434800069312 7471601967191 550975722884262 62052500191160 813732307957173 43310414726925 593170798921272 13943528778153 41064523139350 53199353548538 690540693685207 24578304022436 398021829661972 15381454035329 577511340110093 19765394337307
出力例4
20236569001996128