There are $N$ items, the $i$-th item has a weight of $w_i$ and a value of $v_i$. You have a bag of capacity $W$, meaning you can only take items with sum of weights less than $W$. Choose some items to put into the bag such that the sum of values of the items is maximised, and the bag does not break.

Formally, choose $$\{i_1, i_2, \dots, i_K \} \subseteq \{1, 2, \dots, N \}$$ such that $$\sum_{j=1}^K w_{i_j} \le W$$ and maximises $$V=\sum_{j=1}^K v_{i_j}.$$

Input

The first line of input contains two integers, $N$ and $W$. The following $N$ lines of input contains two integers each, $w_i$ and $v_i$.

Output

Output a single integer, the maximum sum of values of the items.

Constraints

For all testcases:
$1 \le N \le 10^3$
$1 \le W \le 10^3$
$1 \le w_i \le W$
$1 \le v_i \le 10^9$

Subtask 1 (20%): $N, W \le 10$
Subtask 2 (80%): No other constraints