Knapsack 4 - MarisaOJ: Marisa Online Judge

There are

n

$n$ items,

i^{t h}

$i^{th}$ item has the weight of

w_{i}

$w_i$ and value of

v_{i}

$v_i$ . You can choose an arbitrary number items as long as their weight doesn't exceed a given

S

$S$ . Find a way of choosing items so that their value is maximum possible. ### Input - First line contains 2 integers

n

$n$ and

S

$S$ . - Each line in the next

n

$n$ line contains 2 integers

w_{i}

$w_i$ ,

v_{i}

$v_i$ . ### Output - The maximum possible value you can obtain. ### Constraints -

1 \leq n \leq 500

$1 \le n \le 500$ . -

1 \leq S \leq 10^{9}

$1 \le S \le 10^9$ . -

1 \leq w_{i} \leq 10^{9}

$1 \le w_i \le 10^9$ . -

1 \leq v_{i} \leq 500

$1 \le v_i \le 500$ . ### Example Input:

3514412100

$3 5 1 4 4 1 2 100$

Output:

104

$104$

Exchange labels DP
	Knapsack 4
	Longest common subsequence 2

Topic

Dynamic Programming

Rating

1400

Solution (1)

Solution