Informática Avançado - Semana 50 - Problema 1

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

ENTRADA SAÍDA
3 8
3 30
4 50
5 60
90