Alicia, motivada como nunca lo ha estado antes en su vida, ha decidido levantarse de su silla "gamer" de una vez por todas y comenzar una de las rutas de peregrinación pertenecientes al Camino de Santiago, con destino en Santiago de Compostela. Antes de ello, Alicia ha de decidir con qué llenará su vasta mochila, cuyo peso límite no podrá ser superado. O, dicho de otra forma, tiene que decidir qué sabores de Doritos y qué bebidas altas en azúcar se llevará. Así, tu misión consiste en calcular cuántos gramos de azúcar podrá llevarse en total, como máximo, si decide de forma óptima.

Entrada

La primera línea contendrá dos enteros: ~n~ (~1 \le n \le 7 \cdot 10^{3}~), el número de alimentos con los que cuenta Alicia en casa, y ~m~ (~1 \le m \le 7 \cdot 10^{3}~), el peso límite de su mochila.

Las siguientes ~n~ líneas contendrán dos enteros: ~s_{i}~ (~1 \le s_{i} \le 7 \cdot 10^{3}~), los gramos de azúcar en el ~i~-ésimo alimento, y ~w_{i}~ (~1 \le w_{i} \le 7 \cdot 10^{3}~), el peso del ~i~-ésimo alimento (~1 \le i \le n~).

Salida

Se ha de imprimir un entero ~k~, los gramos de azúcar que podrá llevarse en total, como máximo.

Puntuación

• 50 puntos: ~n \le 25~
• 50 puntos: Sin restricciones.

Ejemplo 1

Entrada

4 1200
700 950
450 500
350 350
100 450

Salida

800

Ejemplo 2

Entrada

1 600
350 750

Salida

0