#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

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.

Constraints

$1 \le n \le 100$
$1 \le W \le 10000$
$1 \le w_i, v_i \le 1000$

Input

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

Output

$max$

Samples

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

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.

$1 \le n \le 100$
$1 \le W \le 10000$
$1 \le w_i, v_i \le 1000$

\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$