시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 65 21 21 40.385%

문제

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

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

입력

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

출력

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

예제 입력 1

1
3
3 8 10
1 4 6
6 4 5

예제 출력 1

11

힌트

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

W3sicHJvYmxlbV9pZCI6IjExMTA4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiVFYgXHVjODA0XHVjN2MxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIwOThcdWIyOTQgXHVkMmYwXHViZTQ0XHVhYzAwIFx1ZDU1OFx1YjA5OFx1YmMxNlx1YzVkMCBcdWM1YzZcdWIyOTQgXHVjOWQxXHVjNWQwIFx1YWMwMFx1Yzg3MVx1YWNmYyBcdWQ1NjhcdWFlZDggXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YzViNFx1YjVhNCB0dlx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWJjZmMgXHVjOWMwIFx1YjI5OCBcdWFjMDBcdWM4NzFcdWFjZmMgXHViMmU0XHVkMjJjXHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWI5Y2VcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWM3NzRcdWI5N2MgXHVjNzkwXHViM2Q5XHVjNzNjXHViODVjIFx1ZDU3NFx1YWNiMFx1ZDU3NCBcdWM5MDQgXHVhZTMwXHVhY2M0XHVjNzQ0IFx1YjljY1x1YjRlNFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1YyBcdWQ1NzRcdWIzZDlcdWM1NDggXHViMGI0IFx1YWMwMFx1Yzg3MVx1YjRlNFx1Yzc3NCBcdWJjZjRcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IHR2XHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1YzgxNVx1ZDU3NFx1YzgzOFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHVhYzgzXHViNGU0XHVjNzQwIFx1YjllNFx1YzhmYyBcdWIyOTggXHVhYzE5XHVjNzQwIFx1YzJkY1x1YWMwMVx1YzVkMCBcdWMyZGNcdWM3OTFcdWQ1NzRcdWMxMWMgXHVjODE1XHVkNjU1XHVkNzg4IFx1YWMxOVx1Yzc0MCBcdWMyZGNcdWFjMDFcdWM1ZDAgXHViMDVkXHViMDljXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVkNTVjIFx1YzhmY1x1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjNWI0XHViNWE0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWJjZmMgXHVjOWMwIFx1YzgxNVx1ZDU3NFx1YjE5M1x1YWNlMCBcdWFkZjggXHViYzI5XHVjMmRkXHViMzAwXHViODVjIDFcdWIxNDRcdWFjMDQgXHVjOWM0XHVkNTg5XHVkNTU4XHViYTc0IFx1YjQxOFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWI0ZTRcdWM3NDAgXHVhYzAwXHVjODcxXHViNGU0XHViODVjXHViZDgwXHVkMTMwIFx1Yzc3Y1x1YzgxNVx1ZDU1YyBcdWM4MTBcdWMyMThcdWI5N2MgXHViYzFiXHViMjk0XHViMzcwIFx1Yzc3NCBcdWM4MTBcdWMyMThcdWFjMDAgXHViMTkyXHVjNzQ0IFx1YzIxOFx1Yjg1ZCBcdWFjMDBcdWM4NzFcdWM3NzQgXHVjMTIwXHVkNjM4XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWI3M2JcdWM3NzRcdWI0MWNcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWI0ZTRcdWM3NDQgXHViY2ZjXHViNTRjIFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWNkMWRcdWQ1NjlcdWM3NzQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgdHZcdWMyYTRcdWNmMDBcdWM5MDRcdWM3NDQgXHVjODE1XHVkNTU4XHVhZTMwXHViODVjIFx1YWMwMFx1Yzg3MVx1Yzc3NCBcdWQ1NjlcdWM3NThcdWQ1ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWIwOThcdWIyOTQgXHViMmE1XHViODI1XHVjNzc0IFx1YmQ4MFx1Yzg3MVx1ZDU1OFx1YzVlYyBcdWFjMDBcdWMwYzFcdWM3NTggXHVjNWVjXHVjNzkwXHVjZTVjXHVhZDZjXHVjNWQwXHVhYzhjIFx1Yzc3NCBcdWMyYTRcdWNmMDBcdWM5MDRcdWM3NDQgXHVjNzkwXHViM2Q5XHVjNzNjXHViODVjIFx1YjljY1x1YjRlNFx1YzViNFx1YzhmY1x1YjI5NCBcdWFlMzBcdWFjYzRcdWI5N2MgXHViOWNjXHViNGU0XHVjNWI0XHViMmVjXHViNzdjXHVhY2UwIFx1YmQ4MFx1ZDBjMVx1ZDU4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YWMwMFx1YzBjMVx1Yzc1OCBcdWM1ZWNcdWM3OTBcdWNlNWNcdWFkNmNcdWIzYzQgXHVjNzc0XHVhYzgzXHVjNzc0IFx1YWRjMFx1Y2MyZVx1YzU0NCBcdWM1ZWNcdWI3ZWNcdWJkODRcdWI0ZTRcdWM1ZDBcdWFjOGMgXHViZDgwXHVkMGMxXHVjNzQ0IFx1ZDU1OFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCB0XHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNzQwIHR2XHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzU4IFx1YWMxY1x1YzIxOCBuKDEgJmxlOyBuICZsZTsgMTAwMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBuXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMFx1YzExYyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDFjIDNcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IHMsIGQsIHBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBzXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc1OCBcdWMyZGNcdWM3OTFcdWMyZGNcdWFjMDQsIGRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzU4IFx1YzljMFx1YzE4ZFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWFjZTAgcFx1YjI5NCBcdWFkZjggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWFjMDBcdWM4NzFcdWI0ZTRcdWM3NTggXHVjMTIwXHVkNjM4XHViM2M0XHVjNzc0XHViMmU0LiAoMCAmbGU7IHMgJmx0OyBzK2QgJmxlOyAxMDA4MCwgMSAmbGU7IHAgJmxlOyAyMDAwKSBcdWI5Y2NcdWM1N2QgcytkPWtcdWI3N2NcdWFjZTAgXHVkNTYwXHViNTRjIFx1Yzc3NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDAgXHVjODE1XHVkNjU1XHVkNzg4IGtcdWMyZGNcdWFjMDFcdWM1ZDAgXHViMDVkXHViMDk4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YWNlMCBcdWMwYzggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1YzgxNVx1ZDY1NVx1ZDc4OCBrXHVjMmRjXHVhYzAxXHViZDgwXHVkMTMwIFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmNjNFx1Yjg1YyBcdWQ1NWNcdWM5MDRcdWM1ZDAgXHVjMTIwXHVkNjM4XHViM2M0XHVjNzU4IFx1Y2QxZFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD4xXHViZDgwXHVkMTMwIDRcdWIzZDlcdWM1NDggXHVjOWMwXHVjMThkXHViNDE4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1YWNmYyA2XHViZDgwXHVkMTMwIDRcdWIzZDlcdWM1NDggXHVjOWM0XHVkNTg5XHViNDE4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWJjZjRcdWJhNzQgXHVjMTIwXHVkNjM4XHViM2M0XHVjNzU4IFx1Y2QxZFx1ZDU2OVx1Yzc0MCA2KzU9MTFcdWM3NzQgXHViNDE4XHVhY2UwIFx1Yzc3NFx1YWM4M1x1Yzc3NCBcdWFjMDBcdWM4NzFcdWM3NzQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTIwXHVkNjM4XHViM2M0XHVjNzU4IFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTExMDgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUViBCYXR0bGUiLCJkZXNjcmlwdGlvbiI6IjxwPlRvIHlvdXIgaW1tZW5zZSBmcnVzdHJhdGlvbiwgeW91IG9ubHkgaGF2ZSBvbmUgdGVsZXZpc2lvbiBzZXQgaW4geW91ciBmYW1pbHkuIERlY2lkaW5nIHdoYXQgVFYgc2hvdyB0byB3YXRjaCBhdCBhbnkgZ2l2ZW4gdGltZSBpcyB0aGUgc291cmNlIG9mIGEgbG90IG9mIGFyZ3VtZW50LiBBcyBhbiBleGFtcGxlLCB5b3VyIGxpdHRsZSBzaXN0ZXIgQW5uZSBhbHdheXMgd2FudHMgdG8gd2F0Y2ggJnJkcXVvO0Rlc3BlcmF0ZSBIb3VzZXdpdmVzJnJkcXVvOyB3aGlsZSB5b3Ugd2FudCB0byB3YXRjaCAmcmRxdW87Qy5TLkkuJnJkcXVvOy4gWW91IGJlbGlldmUgaXQgd291bGQgYmUgYmVuZWZpY2lhbCB0byB1c2UgYXV0b21hdGVkIHRvb2xzIHRvIHNldHRsZSB0aGVzZSBhcmd1bWVudHMuPFwvcD5cclxuXHJcbjxwPllvdSB0aGVyZWZvcmUgZGVjaWRlIHRvIGNvbnN0cnVjdCBhIHN5c3RlbSB0aGF0IHdpbGwgZGVjaWRlIHdoaWNoIHNob3cgdGhhdCBzaG91bGQgYmUgb24gYXQgYW55IGdpdmVuIHBvaW50IGluIHRpbWUuIER1cmluZyBhIHNlYXNvbiBlYWNoIHNob3cgaXMgdHlwaWNhbGx5IHNlbnQgb24gdGhlIGV4YWN0IHNhbWUgdGltZSBlYWNoIHdlZWsuIFlvdSB0aGVyZWZvcmUgZGVjaWRlIHRvIHNvbHZlIHRoaXMgcHJvYmxlbSBmb3Igb25lIHdlZWssIGFuZCBsZXQgdGhpcyBzb2x1dGlvbiBkZWNpZGUgZm9yIGEgd2hvbGUgc2Vhc29uLiBFYWNoIG1lbWJlciBvZiB0aGUgZmFtaWx5IGlzIGdpdmVuIHkgcG9pbnRzIHdoaWNoIGhlXC9zaGUgY2FuIGRpc3RyaWJ1dGUgYW1vbmcgaGlzXC9oZXIgZmF2b3JpdGUgc2hvd3MuIFdlIGFzc3VtZSB0aGF0IGVhY2ggc2hvdyBzdGFydHMgYXQgdGhlIHNhbWUgdGltZSBhbmQgbGFzdHMgZm9yIGQgY29uc2VjdXRpdmUgbWludXRlcyBlYWNoIHdlZWsuIEVhY2ggVFYgc2hvdyBpcyB0aGVuIGFzc2lnbmVkIHRoZSB0b3RhbCBudW1iZXIgb2YgcG9pbnRzIGdpdmVuIHRvIGl0IGJ5IGFsbCBmYW1pbHkgbWVtYmVycyBpbiB0b3RhbC4gWW91IHNob3VsZCB3cml0ZSBhIHByb2dyYW0gdGhhdCBtYXhpbWl6ZXMgdGhlIHRvdGFsIG51bWJlciBvZiBwb2ludHMgb2YgdGhlIFRWIHNob3dzIHNob3duIG9uIHlvdXIgdGVsZXZpc2lvbiBzZXQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBnaXZlcyAxICZsZTsgdCAmbGU7IDMwLCB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIFRoZSBmaXJzdCBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZSBnaXZlcyAxICZsZTsgbiAmbGU7IDEwMDAwMCwgdGhlIG51bWJlciBvZiBUViBzaG93cyB0aGF0IGhhdmUgZ290dGVuIGFueSBwb2ludHMgZnJvbSB5b3VyIGZhbWlseS4gVGhlbiBmb2xsb3cgbiBsaW5lcyB3aXRoIDMgc3BhY2Ugc2VwYXJhdGVkIGludGVnZXJzIHM8c3ViPmk8XC9zdWI+LCBkPHN1Yj5pPFwvc3ViPiBhbmQgcDxzdWI+aTxcL3N1Yj4sIHdoZXJlIGVhY2ggbGluZSBkZXNjcmliZXMgb25lIFRWIHNob3cuIHM8c3ViPmk8XC9zdWI+IGRlc2NyaWJlcyB0aGUgbWludXRlIGF0IHdoaWNoIHNob3cgaSBzdGFydHMsIGFuZCBkPHN1Yj5pPFwvc3ViPiBkZXNjcmliZXMgdGhlIG51bWJlciBvZiBtaW51dGVzIHNob3cgaSBsYXN0cyAoMCAmbGU7IHM8c3ViPmk8XC9zdWI+ICZsdDsgczxzdWI+aTxcL3N1Yj4gKyBkPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDgwKS4gSWYgczxzdWI+aTxcL3N1Yj4gKyBkPHN1Yj5pPFwvc3ViPiA9IGssIGl0IG1lYW5zIHRoYXQgeW91IGNhbiBzdGFydCB3YXRjaGluZyBhIG5ldyBzaG93IGF0IHRpbWUgay4gcDxzdWI+aTxcL3N1Yj4gZGVzY3JpYmVzIHRoZSB0b3RhbCBudW1iZXIgb2YgcG9pbnRzIHNob3cgaSBoYXMgZ290dGVuIGluIHlvdXIgZmFtaWx5ICgxICZsZTsgcDxzdWI+aTxcL3N1Yj4gJmxlOyAyMDAwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGVyZSBzaG91bGQgYmUgb25lIGxpbmUgb2Ygb3V0cHV0IGZvciBlYWNoIHRlc3QgY2FzZSBjb250YWluaW5nIHRoZSBtYXhpbXVtIHN1bSBvZiBwb2ludHMgZm9yIHRoZSBUViBzaG93cyBzaG93biBvbiB0aGUgdGVsZXZpc2lvbiBzZXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > IDI Open Contest > IDI Open 2008 B번