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