Intermediário Informática - Semana 4

0 Flares Facebook 0 0 Flares ×

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 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 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, N, com  (1 ≤ P , ≤ 2000)  que representam, respectivamente, quantos gramas de carne Kakariús consegue comer e a quantidade de pedaços no rodízio. As próximas linhas representam os pedaços e contêm, cada uma, dois inteiros menores que 10^9. 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
0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: