Toca-fita X17790

Você vai fazer uma longa viagem de carro, mas precisa gravar umas fitas para escutar no caminho. (Sim, o carro que você vai dirigir não possui cd player) Para gravar a fita, você deve escolher dentre as faixas da sua playlist favorita.

Você deve selecionar um conjunto de músicas que couberem na fita, deixando o mínimo de espaço restante possível, de acordo com as seguintes especificações:

• Cada fita aceita no máximo N minutos de gravação.

• Cada playlist possui no máximo 20 músicas.

• Nenhuma faixa é maior que 1000 minutos.

• Nenhuma faixa pode ser gravada mais de uma vez.

• Cada faixa tem prioridade de acordo com sua ordem na playlist. Ou seja, as músicas que aparecem primeiro têm prioridade sobre as últimas.

O seu programa deve selecionar o conjunto de faixas que preenche melhor a fita, observando a ordem de preferência, e imprimir na mesma ordem em que são apresentadas na playlist.

Input

Há múltiplos casos de teste. Cada linha da entrada contém o valor N (a duração máxima de gravação da fita), o número de faixas e as durações de cada uma.

Por exemplo, na primeira linha: N = 5, número de faixas = 3, primeira faixa dura 1 minuto, a segunda 3 minutos e a última 4 minutos.

Output

Imprima o conjunto de músicas e suas durações e a string ’sum:’ seguida do espaço utilizado da fita.