주차장 할인 적용 순서

문제

한 주차장은 하루 동안 출차한 차량의 요금을 정산한다. 정산 기록에는 각 차량의 주차 시간과 할인 대상 여부가 들어 있다. 차량에는 기록에 등장한 순서대로 1번부터 N번까지 번호를 붙인다. 같은 차량이 다시 방문한 경우에도 서로 다른 기록으로 취급하며, 각 기록의 요금은 다른 기록과 관계없이 계산한다. 주차 시간이 30분 이하이면 기본 요금은 0원이다. 주차 시간이 30분을 초과하고 120분 이하이면, 처음 30분을 제외한 시간을 10분 단위로 계산한다. 이때 10분마다 500원을 부과하며, 남는 시간이 10분보다 짧아도 한 단위로 계산한다. 예를 들어 주차 시간이 31분이면 기본 요금은 500원이다. 주차 시간이 120분을 초과하면 처음 120분에 대한 기본 요금은 4,500원이다. 여기에 120분을 초과한 시간을 20분 단위로 계산하여 단위마다 700원을 더한다. 이 구간에서도 남는 시간이 20분보다 짧으면 한 단위로 계산한다. 앞 구간의 10분 단위 규칙을 120분 이후에 계속 적용하지 않는다. 기본 요금을 구한 다음에는 상한과 할인을 순서대로 적용한다. 먼저 기본 요금이 12,000원을 넘으면 12,000원으로 바꾼다. 그다음 할인 대상 차량이면 해당 금액을 2로 나눈 몫을 최종 요금으로 삼는다. 할인 대상이 아니면 상한을 적용한 금액이 그대로 최종 요금이다. 할인 여부는 무료 주차 시간이나 기본 요금 계산 구간을 바꾸지 않는다. 모든 기록의 최종 요금 합계와 최종 요금이 가장 큰 차량을 구한다. 가장 큰 최종 요금이 같은 차량이 여러 대이면 번호가 가장 작은 차량을 선택한다. 기록이 존재하면 모든 요금이 0원이더라도 차량 한 대를 선택한다. 기록이 하나도 없으면 요금 합계와 최대 요금은 0이며, 선택할 차량 번호는 -1이다.

입력

첫째 줄에 정수 N이 주어진다. 0 ≤ N ≤ 10,000이다.
다음 N개 줄에 각 기록의 주차 시간 T와 할인 표시 D가 주어진다. T는 분 단위 정수이며 1 ≤ T ≤ 1,440이다. D는 0 또는 1이며, 1이면 할인 대상이고 0이면 할인 대상이 아니다.

출력

최종 요금 합계, 가장 큰 최종 요금, 선택한 차량 번호를 이 순서대로 공백으로 구분하여 한 줄에 출력한다. N이 0이면 0 0 -1을 출력한다.

5
30 0
31 0
120 1
121 0
1440 1

13950 6000 5

3
31 0
40 0
10 1

1000 500 1

0

0 0 -1

출처: Devin.KR 자체 제작