Livros

Thiago é um estudante muito dedicado, e por isso, sempre gosta de levar os seus $N$ livros para a escola (mesmo não precisando de todos). Ele recentemente comprou uma nova mochila que, apesar de muito bonita, não aguenta carregar todos os livros. Assim, dados os pesos $w_i$ e os valores de aprendizado $v_i$ de cada livro $i$ $(1 \leq i \leq N)$, ajude o estudante a maximizar o seu aprendizado, de modo que a soma dos pesos dos livros não ultrapassem a capacidade máxima $W$ da mochila.

Entrada

A primeira linha possui dois inteiros, $N$ e $W$.
As próximas $N$ linhas possuem dois inteiros, $w_i$ e $v_i$, respectivamente.

Saída

Imprima um único inteiro, a maior soma de aprendizado possível de modo que a capacidade da mochila não seja ultrapassada.

Restrições

• $1 \leq N \leq 100$
• $1 \leq W \leq 10^9$
• $1 \leq w_i \leq W$
• $1 \leq v_i \leq 10^3$

Exemplo