8346: 大容量 01 背包 II
[Creator : ]
Description
Bobo has n items, where the i-th item has weight $w_i$ and value $v_i$.
He wants to pick some items whose sum of weights does not exceed m, and maximize the sum of values.
He wants to pick some items whose sum of weights does not exceed m, and maximize the sum of values.
Input
The input consists of several test cases terminated by end-of-file.
The first line of each test case contains two integers n and m.
The i-th of the following n lines contains two integers $w_i$ and $v_i$.
The first line of each test case contains two integers n and m.
The i-th of the following n lines contains two integers $w_i$ and $v_i$.
Output
For each test case, print an integer which denotes the result.
Constraints
$1≤n≤2×10^5$
$1 \leq m \leq 2 \times 10^5$
$1 \leq w_i \leq 100$
$1 \leq v_i \leq 10^9$
The sum of n does not exceed $10^6$.
The sum of m does not exceed $10^6$.
$1 \leq m \leq 2 \times 10^5$
$1 \leq w_i \leq 100$
$1 \leq v_i \leq 10^9$
The sum of n does not exceed $10^6$.
The sum of m does not exceed $10^6$.
Sample 1 Input
3 4
1 1
2 2
2 3
3 5
1 1
2 2
2 3
1 10
9 1000000000
Sample 1 Output
5
6
1000000000