SPOJ Brasil

O conhecido e temido hacker SideBarCoder finalmente decidiu entregar-se às autoridades, depois de anos infernizando a vida de administradores de sistemas. SideBarCoder nunca causou prejuízos diretamente, mas deixava os administradores furiosos, tendo ficado famoso por deixar recados humorosos em arquivos localizados em sistemas supostamente impenetráveis.

SideBarCoder aceitou a proposta feita publicamente por uma grande empresa, de um ótimo salário, com a condição de revelar a sua verdadeira identidade e trabalhar dali em diante na melhoria da segurança do sistema Linux. No entanto, a Polícia Federal não foi tão condescendente quanto SideBarCoder esperava e prendeu-o no seu primeiro dia de trabalho.

Felizmente o juiz encarregado do caso levou em consideração o fato de SideBarCoder nunca ter causado prejuízo a nenhuma empresa, e decidiu que ele poderia reduzir o período na cadeia se realizasse trabalho voluntário nas escolas de seu bairro (como pintar paredes de salas de aulas, ajudar a cuidar de bebês em creches, etc).

O juiz entregou a SideBarCoder uma lista de tarefas possíveis. Cada tarefa corresponde a uma certa quantidade de pontos que podem ser utilizados para reduzir a pena. SideBarCoder deve realizar as tarefas no período de uma semana, de segunda-feira a sexta-feira. Para cada tarefa, o juiz especificou o dia e hora de início e de final da tarefa, e o número de pontos correspondente. O número de pontos atribuído à tarefa não é função de sua duração, mas sim de sua dificuldade. Assim, cuidar de uma classe com vinte crianças por duas horas representa um número maior de pontos do que pintar uma sala de aula, que demora quatro horas.

É lógico que SideBarCoder pensou em utilizar um computador para determinar como conseguir o maior número de pontos possível. No entanto, como pena adicional, o juiz determinou que SideBarCoder não pode chegar perto de um computador antes de cumprir sua pena. Desesperado, SideBarCoder solicitou que você escrevesse um programa para determinar quais tarefas ele deveria escolher.

Para ter os pontos contabilizados, uma tarefa deve ser cumprida integralmente (ou seja, do início ao final do período para ela estabelecido, sem interrupção). No conjunto de tarefas selecionado pelo seu programa não pode haver tarefas conflitantes. Duas tarefas conflitam se ambas devem ser executadas no mesmo dia e existir intersecção entre os seus horários. Como todas as tarefas serão realizadas no bairro onde SideBarCoder mora, o tempo de deslocamento de uma tarefa para outra pode ser desconsiderado. Assim, ele pode executar sem conflito duas tarefas A e B tais que o horário de término de A é igual ao horário de iníco de B.

Entrada

A entrada contém vários casos de teste. A primeira linha de um caso de teste contém um inteiro 0 <= N <= 10000 que indica o número de tarefas disponibilizadas pelo juiz. Cada uma das N linhas seguintes descreve uma tarefa, no seguinte formato:

Codigo Pontos Dia Inicio Final

onde

• Codigo é um inteiro que identifica univocamente uma tarefa (1 <= Codigo <= 10000);

• Pontos é um inteiro que indica o número de pontos da tarefa (1 <= Pontos <= 50);

• Dia é uma cadeia de três caracteres que indica o dia da semana (Seg, Ter, Qua, Qui, Sex) da tarefa;

• Início e Final indicam a hora de início e fim da tarefa, no formato HH:MM (entre 00:00 e 23:59). O final de uma tarefa ocorre sempre após o seu início e uma tarefa é inteiramente contida em um dia.

O final da entrada é indicado por N = 0.

Saída

Para cada caso de teste da entrada seu programa deve produzir seis linhas. A primeira linha deve conter a expressão ‘Total de pontos:’, seguida de um espaço, seguida de um inteiro: o número máximo de pontos que SideBarCoder pode acumular. As cinco linhas seguintes da saída devem conter a lista dos pontos a serem conseguidos em cada dia da semana, no formato mostrado no exemplo de saída abaixo.

Exemplo de entrada

3
5000 10 Seg 8:00 23:00
5001 20 Seg 11:00 12:00
5002 15 Seg 23:01 23:30
4
1977 5 Qua 10:00 10:29
1980 10 Qua 10:15 11:15
1983 6 Qua 11:00 12:00
1000 10 Seg 13:00 22:00
0

Saída para o exemplo de entrada

Total de pontos: 35
Seg: 35
Ter: 0
Qua: 0
Qui: 0
Sex: 0
Total de pontos: 21
Seg: 10
Ter: 0
Qua: 11
Qui: 0
Sex: 0