Pedido de Desculpas
Por OBI - Olimpíada Brasileira de Informática 2005 
Brazil
Por OBI - Olimpíada Brasileira de Informática 2005 Brazil
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.
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).
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 |