URI Online Judge | 2498

Ajude Vânia

Por Diego Rangel, FACIT BR Brazil

Timelimit: 1

Rangel é um estudante de engenharia de computação que nas horas vagas (quando não está cheio de coisas da faculdade) gosta de estudar para competições de programação e ler livros. Além de gostar de ler os livros Cormen e dos Halim, ele é muito fã de ficção. Sabendo disso, sua amiga, Vânia decidiu emprestar alguns livros de sua coleção a Rangel para que ele possa ler durante as férias.

Cada i-ésimo livro de Vânia possui um peso wi e vi que representa o provável grau de interesse de Rangel pelo livro. Se dependesse dela, emprestaria todos os seus livros, mas isso é impossível pois sua bolsa não cabe todos os seus livros (que são muitos).

Dado o número de livros de sua estante a máxima carga suportada pela sua bolsa, o peso e o grau de interesse de cada um dos livros, Vânia pede sua ajuda para escrever um programa que ajude a escolher os livros de tal forma que maximize o possível grau de interesse de Rangel pelos livros. Ela poderia fazer isso, mas está muito ocupada com as provas finais.

Entrada

A entrada contém vários casos de teste. Cada caso de teste começa com dois valores N e C (1 ≤ N ≤ 1000) e (1 ≤ C ≤ 100) que representam o número de livros disponíveis na estante de Vânia e a capacidade de sua bolsa respetivamente. Cada uma das próximas N linhas haverá dois inteiros W (1 ≤ WC) e V (1 ≤ V ≤ 1000) que representam respectivamente o peso de cada livro e o grau de interesse de Rangel pelo livro. O final da entrada é determinado com N = C = 0.

Saída

Para cada caso de teste seu programa deverá imprimir uma linha com a seguinte formatação: Caso H: M onde H é um inteiro que indica numero do caso de teste e M é o máximo grau de interesse de Rangel pelos livros.

Exemplo de Entrada Exemplo de Saída

4 30
12 98
13 25
2 97
19 95
5 20
12 98
3 25
12 97
9 95
11 48
0 0

Caso 1: 220
Caso 2: 143