8579: DPL_1_H : Huge Knapsack Problem
[Creator : ]
Description
You have $N$ items that you want to put them into a knapsack. Item $i$ has value $v_i$ and weight $w_i$.
You want to find a subset of items to put such that:
You want to find a subset of items to put such that:
- The total value of the items is as large as possible.
- The items have combined weight at most $W$, that is capacity of the knapsack.
Input
The first line consists of the integers N and W.
In the following $N$ lines, the value and weight of the $i$-th item $v_i,w_i$ are given.
In the following $N$ lines, the value and weight of the $i$-th item $v_i,w_i$ are given.
Output
Print the maximum total values of the items in a line.
Constraints
$1 ≤ N ≤ 40$
$1 ≤ v_i ≤ 10^{15}$
$1 ≤ w_i ≤10^{15}$
$1 ≤ W ≤10^{15}$
$1 ≤ v_i ≤ 10^{15}$
$1 ≤ w_i ≤10^{15}$
$1 ≤ W ≤10^{15}$
Sample 1 Input
4 5
4 2
5 2
2 1
8 3
Sample 1 Output
13
Sample 2 Input
2 20
5 9
4 10
Sample 2 Output
9