Knapsack

Tough Dash, January 2023
Limits 1s, 512 MB

You have a backpack that can carry a maximum weight of CC. You will also be given a set of items, their weights and their values.

Determine the maximum total value of items that you can carry in your backpack.

Input

The input will start with two integers: NN (1N100001 \le N \le 10000), the number of items, and CC (1C1061 \le C \le 10^6) the capacity of your backpack.

The next NN lines will each contain a pair of integers: WiW_i (1Wi1001 \le W_i \le 100), the weight of item ii, and ViV_i (1Vi1001 \le V_i \le 100) the value of item ii.

Output

Print the maximum total value of items that you can carry in your backpack.

Sample

InputOutput
3 5
3 1
2 1
2 2
3

You can take the 2nd and the 3rd items. Their combined weight is 4 (less than the capacity, 5) and their total value is 3.


Submit

Login to submit.

Statistics

66% Solution Ratio
Hare.592016Earliest, 1M ago
rkb_rdFastest, 0.0s
hmdkamrulLightest, 5.7 MB
SyedshakilmahmShortest, 406B
Toph uses cookies. By continuing you agree to our Cookie Policy.