Em Busca do Corpo Perfeito
Kakariús é um jovem físico que busca equilíbrio de corpo e mente. Quando não está resolvendo grandes paradigmas da física moderna, gosta de cuidar da sua saúde. Ele é um grande fã de academias, e faz de tudo para aumentar ainda mais seus músculos. Todos sabemos, é claro, que academia não vale nada se não estiver acompanhada de uma dieta condizente com os objetivos que queremos alcançar. Kakariús, procurando mais força, precisa do máximo possível de proteínas e, por isso, vai almoçar em um rodízio de carnes. Nesse rodízio, existem N pedaços de carne, cada um com um determinado peso e valor proteico, que é a quantidade de gramas de proteína no pedaço. Ele adoraria comer toda a comida, mas como sabemos, tudo em excesso faz mal, e ele sabe que suporta apenas P gramas da carne. Os valores proteicos dos pedaços variam muito (podem ser até zero se for apenas gordura) e é uma terrível falta de educação pedir um pedaço e não comê-lo todo. Dados o valor de P e os N pedaços, com seus respectivos pesos e valores proteicos, determine a maior quantidade de gramas de proteína que Kakariús consegue ingerir, comendo apenas pedaços inteiros.
Entrada
A primeira linha da entrada contêm dois inteiros, P e N, com (1 ≤ P , N ≤ 2000) que representam, respectivamente, quantos gramas de carne Kakariús consegue comer e a quantidade de pedaços no rodízio. As próximas N linhas representam os pedaços e contêm, cada uma, dois inteiros menores que . O primeiro é o peso, em gramas, do pedaço, e o segundo é o seu valor proteico.
Saída
O seu programa deve imprimir um valor inteiro que determina a maior quantidade de gramas de proteína que Kakariús consegue ingerir, seguido de uma quebra de linha.
Exemplo de Entrada | Exemplo de Saída |
400 5 100 80 200 40 300 0 200 50 200 30 |
130 |