시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 50 18 18 39.130%

문제

나는 티비가 하나밖에 없는 집에 가족과 함께 살고 있다. 그래서 어떤 tv프로그램을 볼 지 늘 가족과 다투는 경우가 많다. 따라서 이를 자동으로 해결해 줄 기계을 만들고자 한다.

한 해동안 내 가족들이 보고자 하는 tv프로그램은 정해져있다. 그것들은 매주 늘 같은 시각에 시작해서 정확히 같은 시각에 끝난다. 따라서 한 주에 대해서 어떤 프로그램을 볼 지 정해놓고 그 방식대로 1년간 진행하면 되는 것이다. 각 프로그램들은 가족들로부터 일정한 점수를 받는데 이 점수가 높을 수록 가족이 선호하는 프로그램이라는 뜻이된다. 이러한 프로그램들을 볼때 점수의 총합이 가장 큰 방향으로 tv스케줄을 정하기로 가족이 합의했다. 하지만 나는 능력이 부족하여 가상의 여자친구에게 이 스케줄을 자동으로 만들어주는 기계를 만들어달라고 부탁했다. 하지만 가상의 여자친구도 이것이 귀찮아 여러분들에게 부탁을 하고자 한다.

입력

첫번째 주어지는 t는 테스트 케이스이다. 각 테스트 케이스의 첫줄은 tv프로그램의 개수 n이 주어진다. 그리고 n줄에 걸쳐서 space로 구분된 3개의 integer s, d, p가 주어진다. s는 프로그램의 시작시간, d는 프로그램의 지속시간을 나타내고 p는 그 프로그램에 대한 가족들의 선호도이다. (0<= s < s+d <=10080, 1<=p<=2000) 만약 s+d=k라고 할때 이 프로그램은 정확히 k시각에 끝나는 것이고 새 프로그램을 정확히 k시각부터 볼 수 있다.

출력

각 테스트 케이스 별로 한줄에 선호도의 총합의 최댓값을 출력한다.

예제 입력

1
3
3 8 10
1 4 6
6 4 5

예제 출력

11

힌트

1부터 4동안 지속되는 프로그램과 6부터 4동안 진행되는 프로그램을 보면 선호도의 총합은 6+5=11이 되고 이것이 가족이 얻을 수 있는 선호도의 합의 최대가 된다.

출처

Contest > IDI Open Contest > IDI Open 2008 B번