题目描述

经典0—1背包问题,有n个物品，编号为i的物品的重量为w[i]，价值为c[i]，现在要从这些物品中选一些物品装到一个容量为m的背包中，使得背包内物体在总重量不超过m的前提下价值尽量大。

输入格式

第1行:两个整数，n(物品数量，n≤3500)和m(背包容量,m≤12880)。

第2..n+1行：：每行二个整数w[i]，c[i]，表示每个物品的重量和价值。

输出格式

仅一行，一个数，表示最大总价值。

样例

907 691
414 651
251 630
28 43
469 701
211 881
912 571
471 583
36 614
699 625
859 170
267 923
305 329
381 754
201 796
375 567
600 873
848 399
564 160
705 601
633 379
923 393
180 972
358 99
964 395
397 822
716 455
528 968
724 560
93 116
186 219
14 362
727 498
401 411
436 136
146 409
29 823
252 13
880 194

4448

数据范围与提示

No