URI Online Judge | 2299

Pedido de Desculpas

Por OBI - Olimpíada Brasileira de Informática 2005 BR Brazil

Timelimit: 1

Cuca saiu para jogar futebol com os amigos e esqueceu do encontro que tinha com a namorada. Ciente da mancada, Cuca deseja elaborar um pedido especial de desculpas. Resolveu então enviar flores e usar o cartão da floricultura para escrever um pedido especial de desculpas.

Cuca buscou na internet um conjunto de frases bonitas contendo a palavra ‘desculpe’ (que pode ocorrer mais de uma vez na mesma frase). No entanto, o cartão da floricultura é pequeno, e nem todas as frases que Cuca colecionou poderão ser aproveitadas.

Cuca quer aproveitar o espaço do cartão, onde cabe um número limitado de caracteres, para escrever um sub-conjunto das frases coletadas de modo que apareça o máximo de vezes possível a palavra ‘desculpe’.

Escreva um programa que, dados o número de caracteres que cabem no cartão e a quantidade de frases coletadas (com os respectivos comprimentos e os números de ocorrências da palavra ‘desculpe’), determine o número máximo de vezes que a palavra aparece, utilizando apenas as frases colecionadas, sem repetí-las.

Entrada

A entrada é constituída de vários casos de teste. A primeira linha de um caso de teste contém dois números inteiros C e F indicando respectivamente o comprimento do cartão em caracteres (8 ≤ C ≤ 1000) e o número de frases coletadas (1 ≤  F ≤50). Cada uma das F linhas seguintes descreve uma frase coletada. A descrição é composta por dois inteiros N e D que indicam respectivamente o número de caracteres na frase (8 <= N <= 200) e quantas vezes a palavra ‘desculpe’ ocorre na frase (1 ≤ D ≤ 25). O final da entrada é indicado por C = F = 0.

A entrada deve ser lida do dispositivo de entrada padrão (normalmente o teclado).

Saída

Para cada caso de teste seu programa deve produzir três linhas na saída. A primeira identifica o conjunto de teste no formato “Teste n”, onde n é numerado a partir de 1. A segunda linha deve conter o máximo número de vezes que a palavra ‘desculpe’ pode aparecer no cartão, considerando que apenas frases coletadas podem ser utilizadas, e cada frase não é utilizada mais de uma vez. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

A saída deve ser escrita no dispositivo de saída padrão (normalmente a tela).

Exemplo de Entrada Exemplo de Saída

200 4

100 4

100 1

120 2

80 5

40 3

10 1

10 1

20 2

0 0

Teste 1

9


Teste 2

4