형량 감축

악명 높은 해커 SideBarCoder는 수년 동안 시스템 관리자들을 괴롭힌 끝에 마침내 당국에 자수하기로 했다. SideBarCoder가 직접 피해를 입힌 적은 없지만, 뚫을 수 없다고 여겨지던 시스템의 파일에 익살스러운 메모를 남겨 관리자를 격분하게 만든 것으로 유명했다.

SideBarCoder는 한 대기업이 공개적으로 내건 제안을 받아들였다. 조건은 두 가지였다. 진짜 신원을 밝힐 것, 그리고 그 뒤로 Linux 시스템의 보안을 개선하는 일을 할 것. 대가는 아주 좋은 급여였다. 그러나 연방 경찰은 SideBarCoder의 기대만큼 관대하지 않았고, 출근 첫날 그를 체포했다.

다행히 사건을 맡은 판사는 SideBarCoder가 어떤 회사에도 피해를 준 적이 없다는 점을 참작했다. 그래서 동네 학교에서 자원봉사(교실 벽 칠하기, 어린이집에서 아기 돌보기 등)를 하면 수감 기간을 줄일 수 있다고 판결했다.

판사는 SideBarCoder에게 할 수 있는 작업의 목록을 건넸다. 각 작업에는 형량을 줄이는 데 쓸 수 있는 점수가 정해져 있다. SideBarCoder는 월요일부터 금요일까지 한 주 안에 작업을 수행해야 한다. 판사는 작업마다 요일, 시작 시각, 종료 시각, 점수를 지정했다. 작업의 점수는 걸리는 시간이 아니라 난이도로 정해진다. 그래서 아이 스무 명이 있는 반을 두 시간 동안 돌보는 일이 네 시간 걸리는 교실 칠하기보다 점수가 높다.

SideBarCoder는 당연히 컴퓨터로 가장 많은 점수를 얻는 방법을 찾으려 했다. 하지만 판사는 추가 처벌로 형기를 마칠 때까지 컴퓨터 가까이에 가지 못하게 했다. 절박해진 SideBarCoder는 어떤 작업을 골라야 하는지 알려 주는 프로그램을 작성해 달라고 여러분에게 부탁했다.

점수를 인정받으려면 작업을 처음부터 끝까지 중단 없이 모두 수행해야 한다. 여러분의 프로그램이 고른 작업 중에는 서로 충돌하는 작업이 있으면 안 된다. 두 작업이 같은 요일에 있고 시간대가 겹치면 두 작업은 충돌한다. 모든 작업은 SideBarCoder가 사는 동네에서 이루어지므로 작업 사이의 이동 시간은 무시한다. 따라서 A의 종료 시각과 B의 시작 시각이 같은 두 작업 A, B는 충돌 없이 모두 수행할 수 있다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 판사가 제시한 작업의 수를 나타내는 정수 $N$ ($0 \le N \le 10000$)이 주어진다. 다음 $N$개의 줄에는 작업이 한 줄에 하나씩 다음 형식으로 주어진다.

Codigo Pontos Dia Inicio Final

각 항목의 뜻은 다음과 같다.

• Codigo는 작업을 유일하게 식별하는 정수이다 ($1 \le$ Codigo $\le 10000$).
• Pontos는 작업의 점수를 나타내는 정수이다 ($1 \le$ Pontos $\le 50$).
• Dia는 작업의 요일을 나타내는 세 글자 문자열로, Seg(월), Ter(화), Qua(수), Qui(목), Sex(금) 중 하나이다.
• Inicio와 Final은 작업의 시작 시각과 종료 시각이며 HH:MM 형식이다(00:00 이상 23:59 이하). 시가 한 자리이면 8:00처럼 한 자리로 주어질 수 있다. 작업의 종료 시각은 항상 시작 시각보다 늦고, 한 작업은 하루 안에 모두 포함된다.

입력의 끝은 $N = 0$으로 나타낸다.

각 테스트 케이스마다 여섯 줄을 출력한다. 첫 줄에는 Total de pontos:, 공백 하나, 정수 하나를 차례로 출력한다. 이 정수는 SideBarCoder가 모을 수 있는 점수의 최댓값이다. 다음 다섯 줄에는 월요일부터 금요일까지 각 요일에 얻는 점수를 아래 형식으로 출력한다.

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

요일별 점수는 그 요일의 작업만으로 얻을 수 있는 점수의 최댓값이며, 다섯 값의 합은 첫 줄의 값과 같다.