Semana de Provas

1202
Tempo Limite: 5 | Nível: 4

Descrição

Samanta, aluna da Fatec SJC, se sentindo despreparada para a semana de provas, resolveu pegar alguns livros na Biblioteca para estudar durante o final de semana. Esperta, antes de pegar os livros, ela fez uma lista com todos os que gostaria de ler e os agrupou por assuntos diferentes, assim ficaria mais fácil de perguntar aos seus colegas quanto tempo eles gastaram para ler cada grupo de livro.

Com sua lista completa, Samanta está com dificuldade em saber qual é o maior número de livros que ela pode pegar para ocupar o máximo possível do seu final de semana (48h). Então ela pediu para você escrever um programinha que de a resposta para ela.


Entrada

A entrada contém vários casos de teste. Cada caso de teste contém na primeiro linha um valor inteiro N(1 <= N <= 20) que indica o número de assuntos que ela quer estudar. Cada uma das próximas N linhas contém um assunto diferente com dois inteiro X e Y (1 <= X <= 10 e 1 <= Y <= 48 ) representando respectivamente o número de livros e o tempo, em horas, que seus amigos levaram para ler cada grupo. O final da entrada é determinado por N = 0, e não deverá ser processado.


Saída

Para cada caso de teste de entrada deve ser impresso # livro(s), onde # é o máximo de livros que Samanta irá levar para casa.


Exemplos de Entrada Exemplos de Saída

10
2 10
3 5
2 5
3 10
4 20
10 40
5 5
9 9
7 7
6 6
6
5 15
4 23
2 21
4 16
5 19
2 18
0

35 livro(s)
10 livro(s)

Efetue Login ou Cadastre-se para submeter uma solução.



Criado por Marcos Vinicius Costa Bustamante | Adaptado por Erich Rodrigues | Competição: FATEC SJC - Maratona interna 2015