There are \(N\) items, with item \(i\) having weight \(w_i\) and value \(v_i\). Find the maximal possible value of any subset of items such that the sum of their weights does not exceed \(W\).

Constraints

\(1 \leq N \leq 100\)

\(1 \leq w_{i} \leq W \leq 10^{5}\)

\(1 \leq v_{i} \leq 10^{9}\)

Input Specification

The first line contains two integers, \(N\) and \(W\).

The next \(N\) lines contain two integers, \(w_i\) and \(v_{i}\).

Output Specification

Output one integer, the maximal value.

Sample Input

3 8
3 3
4 5
5 6

Sample Output

9

Explaination for Sample Output

The maximal value is when items \(1\) and \(3\) are taken. It can be shown that a higher value is impossible.