Hay \(N\) artículos, numerados \(1, 2, \ldots, N\). Para cada \(i\) (\(1 \leq i \leq N\)), el artículo \(i\) tiene un peso \(w_i\) y un valor \(v_i\).

Taro ha decidido elegir algunos de los \(N\) artículos y llevarlos a casa en una mochila. La capacidad de la mochila es \(W\), lo que significa que la suma de los pesos de los artículos elegidos debe ser a lo sumo \(W\).

Encontrar la suma máxima posible de los valores de los artículos que Taro lleva a casa.

Entrada

La primera línea contiene dos enteros \(N\) y \(W\), la cantidad de artículos y la capacidad de la mochila (\(1 \leq N \leq 100\), \(1 \leq W \leq 10^5\)).

Cada una de las siguientes \(N\) líneas contiene dos enteros \(w_i\) y \(v_i\), el peso y el valor del artículo \(i\) (\(1 \leq w_i \leq W\), \(1 \leq v_i \leq 10^9\)).

Salida

Imprimir un solo número: el valor total máximo posible.

Ejemplo 1

Entrada

3 8
3 30
4 50
5 60

Salida

90

Explicación: se deben elegir los artículos \(1\) y \(3\). Entonces, la suma de pesos es \(3 + 5 = 8\), y la suma de valores es \(30 + 60 = 90\).

Ejemplo 2

Entrada

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Salida

5000000000

Nota: la respuesta puede no caber en un entero de 32 bits.

Ejemplo 3

Entrada

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Salida

17

Explicación: se deben elegir los artículos \(2, 4\) y \(5\). Entonces, la suma de pesos es \(5 + 6 + 3 = 14\), y la suma de valores es \(6 + 6 + 5 = 17\).