你有一个容量为 $V$ 的背包，以及 $n$ 种物品。第 $i$ 种物品的体积为 $w_i$，价值为 $val_i$。

每种物品都有无限件，你可以选择任意多件放入背包，但总容量不能超过 $V$。

请你求出在不超过背包容量的前提下，能获得的最大总价值。

形式化题意：设第 $i$ 种物品选择 $x_i$ 件（$x_i$ 为非负整数），则需要满足：

$$\sum_{i=1}^{n} x_i \cdot w_i \le V,\quad x_i \ge 0$$

最大化目标：

$$\max \sum_{i=1}^{n} x_i \cdot val_i$$

输入格式

第一行两个整数 $n, V$，表示物品种类数与背包容量。

接下来 $n$ 行，每行两个整数 $w_i, val_i$，分别表示第 $i$ 种物品的体积与价值。

输出格式

输出一个整数，表示最大总价值。

3 10
2 3
3 4
4 5

15

1 1
126 587

0

1000 1000
536 405
659 805
713 41
853 253
918 635
432 654
451 484
388 726
830 416
641 142
126 735
276 568
743 623
736 628
725 196
787 131
327 36
142 20
458 143
472 200
522 437
397 859
984 359
951 935
730 610
76 420
134 877
192 715
634 629
125 98
907 898
80 187
979 181
196 754
676 375
947 396
992 798
408 774
197 278
979 553
423 449
970 537
280 110
622 300
788 950
550 658
806 322
588 723
283 92
388 858
13 356
583 109
436 961
358 959
927 66
993 578
844 144
373 987
328 202
316 159
489 238
701 686
499 546
461 818
938 863
936 750
282 886
438 109
569 174
255 535
55 72
93 396
516 357
813 804
669 59
882 254
105 592
356 960
755 471
139 786
32 863
992 453
949 789
479 823
779 791
131 111
532 269
881 370
397 155
26 973
307 789
739 549
72 824
372 794
305 61
579 318
915 389
637 838
834 552
818 773
858 282
581 238
726 510
459 900
912 794
936 373
529 784
134 212
915 691
345 972
579 524
168 957
708 380
209 804
695 625
407 629
692 531
843 961
977 494
21 22
490 801
387 312
901 711
557 88
800 159
308 691
434 541
546 25
776 445
395 611
755 792
627 289
50 859
255 198
41 457
326 195
282 282
535 715
665 368
824 59
214 754
724 615
837 724
825 784
396 320
978 857
625 175
82 737
95 938
162 312
700 145
643 698
5 650
317 383
470 219
96 259
966 24
342 25
671 188
65 376
116 874
238 476
665 502
800 856
583 148
779 402
430 368
445 943
201 708
660 171
446 369
440 14
870 474
342 772
302 275
662 957
907 442
138 373
427 298
553 490
933 441
190 368
274 244
151 219
914 18
340 336
194 466
488 580
391 31
757 519
351 194
946 869
229 464
59 190
746 680
862 587
637 941
80 564
860 324
290 168
24 929
198 523
704 494
507 343
251 952
36 486
11 965
977 715
169 511
184 215
768 832
935 180
305 978
182 280
829 280
868 502
348 210
739 936
687 163
588 19
879 911
195 102
142 927
964 667
588 873
616 34
404 126
230 779
625 94
906 778
497 878
450 347
593 778
171 881
302 315
369 843
790 831
223 329
680 266
560 654
801 914
572 420
588 812
800 637
232 241
691 620
623 257
226 32
212 110
956 431
404 316
312 576
881 258
326 764
799 705
226 952
473 607
550 623
467 873
249 362
790 963
632 781
256 133
843 741
233 53
879 185
630 956
185 342
681 298
785 175
612 884
416 194
801 164
336 846
940 152
652 23
71 646
730 451
207 495
712 18
270 666
695 462
383 24
242 718
562 991
608 304
740 153
12 576
320 603
676 308
72 784
772 746
13 41
782 169
737 518
438 87
574 501
415 330
360 175
863 775
809 398
912 155
532 494
204 84
665 446
666 349
929 748
18 559
699 913
337 739
271 612
971 580
659 357
869 758
63 104
259 423
916 394
294 530
8 505
953 431
634 616
191 770
792 624
207 131
816 628
791 214
336 954
635 229
432 637
9 589
498 948
290 773
829 873
257 827
916 294
338 189
930 903
517 863
469 800
981 819
955 56
622 520
376 761
977 574
579 377
158 352
152 565
531 331
652 729
389 559
1 156
902 912
57 921
889 995
273 234
799 294
455 313
72 625
970 959
572 860
380 158
972 547
822 679
978 813
61 118
264 641
633 300
458 521
768 977
936 769
80 937
639 28
903 673
927 547
779 848
450 436
439 883
38 292
634 40
838 788
902 104
777 849
222 275
708 52
24 824
261 15
807 133
813 427
746 337
83 296
362 573
958 417
8 336
410 360
325 520
951 196
368 879
271 762
145 529
181 871
273 160
591 595
503 382
657 330
216 948
407 3
315 528
382 627
166 174
479 367
954 748
756 496
927 28
55 5
476 314
27 161
501 499
232 636
976 601
654 888
640 27
731 525
381 614
129 215
976 522
300 537
961 154
195 143
755 476
750 773
876 997
912 869
71 270
800 328
462 930
839 608
785 12
63 808
735 469
483 366
275 151
239 578
817 681
471 81
529 715
621 917
692 184
758 142
297 638
956 136
873 655
303 537
834 977
566 94
774 369
828 194
31 152
540 713
657 791
763 939
642 988
453 840
38 311
616 274
809 942
179 49
82 246
119 725
430 475
797 620
603 697
351 4
265 600
52 787
70 182
466 588
227 927
398 183
711 167
763 194
270 5
343 63
918 854
181 94
545 215
836 381
584 3
507 403
636 282
761 985
816 475
834 705
526 925
419 85
36 814
6 831
806 547
527 400
4 316
289 54
511 228
866 81
326 887
349 474
177 132
500 518
802 110
948 33
716 3
784 413
234 574
44 981
700 704
683 495
724 339
529 192
847 143
526 327
955 362
336 98
513 374
11 394
19 471
385 392
841 743
666 806
1 27
563 307
497 54
852 839
474 668
986 289
799 707
152 657
633 512
223 124
894 408
495 710
735 510
754 393
911 601
917 903
223 869
833 858
512 223
850 641
715 636
587 812
462 568
478 61
991 884
287 540
338 624
97 523
389 699
72 207
646 226
53 180
590 789
976 700
604 356
79 187
402 608
321 36
583 592
112 747
577 921
321 35
343 983
602 214
80 292
733 673
471 679
367 571
24 398
661 490
38 80
745 371
393 220
325 350
190 202
350 316
102 93
748 618
576 659
946 869
310 106
195 356
304 433
742 459
705 765
848 924
570 464
305 574
843 255
718 42
364 394
309 256
511 7
323 948
635 62
505 127
641 352
349 233
677 619
500 546
432 499
73 756
826 277
902 726
4 63
145 398
15 205
368 156
565 821
105 11
761 909
205 57
22 570
877 622
818 324
301 513
217 427
504 183
266 508
291 560
136 165
468 182
969 153
868 341
473 414
273 209
81 424
1 474
867 235
642 999
456 138
88 494
430 485
508 253
406 730
119 132
111 347
585 791
357 841
341 263
429 429
154 683
604 385
758 734
361 82
701 235
444 853
124 13
814 763
106 553
368 272
615 232
797 726
8 922
631 253
953 828
521 751
352 285
615 951
510 263
687 87
139 41
61 917
125 634
857 274
895 815
33 234
943 657
739 115
627 85
898 373
606 315
82 96
415 741
220 476
217 456
892 120
223 196
991 927
684 767
25 812
46 359
853 296
205 585
210 599
328 415
471 357
560 990
961 665
930 470
969 888
475 40
766 12
867 727
602 80
441 756
555 585
514 331
594 158
184 714
202 853
928 531
346 325
416 406
50 204
18 748
456 607
239 66
8 938
854 770
134 188
42 977
115 130
748 107
853 188
739 825
550 974
966 324
7 3
950 173
791 551
391 80
313 413
269 152
436 208
358 486
714 234
154 809
335 361
29 170
249 540
813 779
530 442
388 173
520 216
421 462
6 147
563 544
567 542
164 520
66 81
452 588
54 613
8 350
677 946
323 119
862 945
147 648
301 783
737 26
992 595
493 858
420 930
651 168
207 694
3 610
995 545
575 596
788 175
937 638
15 695
435 997
140 915
428 955
285 337
624 428
555 991
83 445
57 82
356 750
6 181
882 406
815 843
635 991
819 194
37 12
627 86
349 135
421 452
621 759
356 266
250 683
225 868
33 548
144 857
880 419
988 429
284 535
93 25
951 961
564 689
410 305
723 77
113 505
544 396
12 149
573 867
679 312
619 775
565 479
752 853
630 983
222 791
758 383
428 89
297 567
830 935
50 650
991 33
146 995
368 720
327 250
69 807
428 342
764 207
634 408
913 159
745 406
392 426
248 99
586 27
656 836
258 112
631 867
522 768
593 546
660 368
565 780
737 997
132 154
870 105
119 728
336 837
201 426
62 958
969 980
108 476
945 956
102 937
148 668
700 387
793 41
306 532
449 618
215 568
712 544
996 6
993 461
277 165
988 136
283 644
27 65
503 239
11 356
822 5
28 476
570 626
808 277
769 699
675 517
936 639
743 348
983 489
995 365
310 117
367 38
21 455
349 55
460 697
342 479
510 581
480 481
100 963
155 406
11 70
582 622
807 270
991 655
438 784
348 827
100 261
716 109
897 899
647 612
189 246
534 529
318 241
287 572
739 984
734 178
880 223
399 267
448 454
296 926
117 157
227 282
593 757
515 321
883 371
245 766
601 205
396 741
673 905
221 908
249 319
683 896
603 738
357 552
38 652
441 988
244 669
316 377
384 97
525 974
831 573
158 173
201 943
238 402
429 46
43 379
640 403
546 243
598 810
940 898
895 315
229 658
295 114
124 357
403 847
476 996
714 645
323 512
667 746
600 111
390 759
916 621
150 60
484 932
385 379
354 734
41 414
191 718
859 320
512 624
268 637
784 948
966 987
761 587
780 399
574 720
533 217
874 339
379 653
437 27
525 551
908 568
448 39
695 949
937 385
657 698
655 726
118 346
481 671
762 870
724 661
984 155
441 134
240 675
954 662
264 128
706 338
581 671
51 65
875 965
389 688
254 707
337 409
524 503
369 830
476 336
626 2
408 84
820 527
703 724
442 131
319 515
310 36
315 343
756 956
444 574
89 917
7 224
857 137
150 424

474000

说明/提示

样例说明 #1

一种最优方案是选择第 1 种物品 $5$ 件：

• 总体积 $5 \times 2 = 10 \le 10$
• 总价值 $5 \times 3 = 15$

数据范围

对于 $40\%$ 的数据，$1\le n \le 8$，$1\le V \le 12$，且对所有 $i$，$1\le w_i \le 1000$，$0\le val_i \le 1000$。

对于 $100\%$ 的数据，$1\le n \le 1000$，$1\le V \le 1000$，且对所有 $i$，$1\le w_i \le 1000$，$0\le val_i \le 1000$。