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

0/1 Knapsack - Classic Problems | Repovive

CLS5. 0/1 Knapsack

1s256 MB

You have $n$ items. Item $i$ has weight $w_i$ and value $v_i$ . Each item can be used at most once.

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 220.

Output

Input

Explanation

For this input, the required output is 90.

Output

Input

Explanation

For this input, the required output is 130.

Output

You have $n$ items. Item $i$ has weight $w_i$ and value $v_i$ . Each item can be used at most once.

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$