Unbounded Knapsack - Classic Problems | Repovive

CLS4. Unbounded Knapsack

1s256 MB

You have $n$ types of items. Item type $i$ has weight $w_i$ and value $v_i$ . You can use each type unlimited times.

Given a knapsack with capacity $W$ , find the maximum total value you can carry.

\begin{array}{l} n \quad W \\ w_1 \quad v_1 \\ w_2 \quad v_2 \\ \vdots \\ w_n \quad v_n \end{array}

$max$

Input

Explanation

For this input, the required output is 12.

Output

Input

2 10
5 10
4 40

Explanation

For this input, the required output is 80.

Output

Input

1 3
2 5

Explanation

For this input, the required output is 5.

Output

1s256 MB

You have $n$ types of items. Item type $i$ has weight $w_i$ and value $v_i$ . You can use each type unlimited times.

Given a knapsack with capacity $W$ , find the maximum total value you can carry.

\begin{array}{l} n \quad W \\ w_1 \quad v_1 \\ w_2 \quad v_2 \\ \vdots \\ w_n \quad v_n \end{array}

$max$

Input

Explanation

For this input, the required output is 12.

Output

Input

2 10
5 10
4 40

Explanation

For this input, the required output is 80.

Output

Input

1 3
2 5

Explanation

For this input, the required output is 5.

Output