시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB7414920.000%

문제

N(1 ≤ N ≤ 10,000)개의 정류장을 지나는 버스가 있다. 정류장은 차례로 1, 2, …, N번의 번호가 붙어 있고, 버스는 1번 정류장에서 출발하여 N번 정류장까지 간 후, 다시 1번 정류장으로 돌아오게 된다.

버스회사에서는 주기적으로 1번 정류장에서 버스를 출발시켜서 모든 손님들이 버스를 이용할 수 있도록 하고 있었는데, 겨울철에 눈이 많이 오는 바람에 한 대의 버스밖에 운행하지 못 하게 되었다. 불행 중 다행으로 회사에서는 고객들이 버스를 이용하는 구간을 K(1 ≤ K ≤ 50,000)개 조사해 둔 상태이다.

버스는 최대 C(1 ≤ C ≤ 100)명을 태울 수 있다. 회사 측에서는 사전에 조사해 둔 자료를 바탕으로, 한 바퀴를 도는(1번 정류장에서 N번 정류장까지 갔다가 다시 1번 정류장으로 돌아오는) 동안 가급적이면 많은 고객들을 목적지까지 태워 주려고 한다. 각 정류장에서 버스는 사람을 내려 줄 수도 있고, 사람을 태울 수도 있다. 단, 버스에 한 밴 태운 고객들은 목적지에 도착하기 전에는 내려줄 수 없다.

목적지까지 태워줄 수 있는 고객의 최대 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 K, N, C가 주어진다. 다음 K개의 줄에는 고객들의 버스 이용 구간을 나타내는 세 정수 S, E(1 ≤ S, E ≤ N), M(1 ≤ M ≤ C)이 주어진다. S와 E는 서로 다르며, 이는 S번 정류장에서 E번 정류장까지 가려는 고객이 M명 있다는 의미이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

4 8 3
1 3 2
2 8 3
4 7 1
8 3 2

예제 출력 1

6

힌트

1번 정류장에서 3번 정류장으로 가는 고객을 두 명 태운다. 2번 정류장에서는 8번 정류장으로 가는 고객을 한 명 태운다(세 명을 다 태울 필요는 없다). 3번 정류장에서 두 명의 고객을 내려 주고, 4번 정류장에서는 7번 정류장으로 가는 고객을 한 명 태운다. 7번 정류장에서 한 명의 고객을 내려 주고, 8번 정류장에서 남은 한 명의 고객을 내려 준 뒤, 3번 정류장으로 가는 고객을 두 명 태운다. 이 고객들을 3번 정류장에 내려 주고, 다시 1번 정류장으로 돌아온다.

W3sicHJvYmxlbV9pZCI6IjIxOTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjODRcdWMyYTRcdWM2NDAgXHVjMTkwXHViMmQ4IiwiZGVzY3JpcHRpb24iOiI8cD5OKDEgJmxlOyBOICZsZTsgMTAsMDAwKVx1YWMxY1x1Yzc1OCBcdWM4MTVcdWI5NThcdWM3YTVcdWM3NDQgXHVjOWMwXHViMDk4XHViMjk0IFx1YmM4NFx1YzJhNFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YzgxNVx1Yjk1OFx1YzdhNVx1Yzc0MCBcdWNjMjhcdWI4NDBcdWI4NWMgMSwgMiwgJmhlbGxpcDssIE5cdWJjODhcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YmQ5OVx1YzViNCBcdWM3ODhcdWFjZTAsIFx1YmM4NFx1YzJhNFx1YjI5NCAxXHViYzg4IFx1YzgxNVx1Yjk1OFx1YzdhNVx1YzVkMFx1YzExYyBcdWNkOWNcdWJjMWNcdWQ1NThcdWM1ZWMgTlx1YmM4OCBcdWM4MTVcdWI5NThcdWM3YTVcdWFlNGNcdWM5YzAgXHVhYzA0IFx1ZDZjNCwgXHViMmU0XHVjMmRjIDFcdWJjODggXHVjODE1XHViOTU4XHVjN2E1XHVjNzNjXHViODVjIFx1YjNjY1x1YzU0NFx1YzYyNFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmM4NFx1YzJhNFx1ZDY4Y1x1YzBhY1x1YzVkMFx1YzExY1x1YjI5NCBcdWM4ZmNcdWFlMzBcdWM4MDFcdWM3M2NcdWI4NWMgMVx1YmM4OCBcdWM4MTVcdWI5NThcdWM3YTVcdWM1ZDBcdWMxMWMgXHViYzg0XHVjMmE0XHViOTdjIFx1Y2Q5Y1x1YmMxY1x1YzJkY1x1Y2YxY1x1YzExYyBcdWJhYThcdWI0ZTAgXHVjMTkwXHViMmQ4XHViNGU0XHVjNzc0IFx1YmM4NFx1YzJhNFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjNjNFx1Yjg1ZCBcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNWM4XHViMjk0XHViMzcwLCBcdWFjYThcdWM2YjhcdWNjYTBcdWM1ZDAgXHViMjA4XHVjNzc0IFx1YjljZVx1Yzc3NCBcdWM2MjRcdWIyOTQgXHViYzE0XHViNzhjXHVjNWQwIFx1ZDU1YyBcdWIzMDBcdWM3NTggXHViYzg0XHVjMmE0XHViYzE2XHVjNWQwIFx1YzZiNFx1ZDU4OVx1ZDU1OFx1YzljMCBcdWJhYmIgXHVkNTU4XHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC4gXHViZDg4XHVkNTg5IFx1YzkxMSBcdWIyZTRcdWQ1ODlcdWM3M2NcdWI4NWMgXHVkNjhjXHVjMGFjXHVjNWQwXHVjMTFjXHViMjk0IFx1YWNlMFx1YWMxZFx1YjRlNFx1Yzc3NCBcdWJjODRcdWMyYTRcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTU4XHViMjk0IFx1YWQ2Y1x1YWMwNFx1Yzc0NCBLKDEgJmxlOyBLICZsZTsgNTAsMDAwKVx1YWMxYyBcdWM4NzBcdWMwYWNcdWQ1NzQgXHViNDU0IFx1YzBjMVx1ZDBkY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzg0XHVjMmE0XHViMjk0IFx1Y2Q1Y1x1YjMwMCBDKDEgJmxlOyBDICZsZTsgMTAwKVx1YmE4NVx1Yzc0NCBcdWQwZGNcdWM2YjggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNjhjXHVjMGFjIFx1Y2UyMVx1YzVkMFx1YzExY1x1YjI5NCBcdWMwYWNcdWM4MDRcdWM1ZDAgXHVjODcwXHVjMGFjXHVkNTc0IFx1YjQ1NCBcdWM3OTBcdWI4Y2NcdWI5N2MgXHViYzE0XHVkMGQ1XHVjNzNjXHViODVjLCBcdWQ1NWMgXHViYzE0XHVkMDM0XHViOTdjIFx1YjNjNFx1YjI5NCgxXHViYzg4IFx1YzgxNVx1Yjk1OFx1YzdhNVx1YzVkMFx1YzExYyBOXHViYzg4IFx1YzgxNVx1Yjk1OFx1YzdhNVx1YWU0Y1x1YzljMCBcdWFjMTRcdWIyZTRcdWFjMDAgXHViMmU0XHVjMmRjIDFcdWJjODggXHVjODE1XHViOTU4XHVjN2E1XHVjNzNjXHViODVjIFx1YjNjY1x1YzU0NFx1YzYyNFx1YjI5NCkgXHViM2Q5XHVjNTQ4IFx1YWMwMFx1YWUwOVx1YzgwMVx1Yzc3NFx1YmE3NCBcdWI5Y2VcdWM3NDAgXHVhY2UwXHVhYzFkXHViNGU0XHVjNzQ0IFx1YmFhOVx1YzgwMVx1YzljMFx1YWU0Y1x1YzljMCBcdWQwZGNcdWM2Y2MgXHVjOGZjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1YzgxNVx1Yjk1OFx1YzdhNVx1YzVkMFx1YzExYyBcdWJjODRcdWMyYTRcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzQ0IFx1YjBiNFx1YjgyNCBcdWM5MDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YWNlMCwgXHVjMGFjXHViNzhjXHVjNzQ0IFx1ZDBkY1x1YzZiOCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWIyZTgsIFx1YmM4NFx1YzJhNFx1YzVkMCBcdWQ1NWMgXHViYzM0IFx1ZDBkY1x1YzZiNCBcdWFjZTBcdWFjMWRcdWI0ZTRcdWM3NDAgXHViYWE5XHVjODAxXHVjOWMwXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YWUzMCBcdWM4MDRcdWM1ZDBcdWIyOTQgXHViMGI0XHViODI0XHVjOTA0IFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOVx1YzgwMVx1YzljMFx1YWU0Y1x1YzljMCBcdWQwZGNcdWM2Y2NcdWM5MDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjZTBcdWFjMWRcdWM3NTggXHVjZDVjXHViMzAwIFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMTM4IFx1YzgxNVx1YzIxOCBLLCBOLCBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIEtcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWNlMFx1YWMxZFx1YjRlNFx1Yzc1OCBcdWJjODRcdWMyYTQgXHVjNzc0XHVjNmE5IFx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOCBTLCBFKDEgJmxlOyBTLCBFICZsZTsgTiksIE0oMSAmbGU7IE0gJmxlOyBDKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFNcdWM2NDAgRVx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc0XHViYTcwLCBcdWM3NzRcdWIyOTQgU1x1YmM4OCBcdWM4MTVcdWI5NThcdWM3YTVcdWM1ZDBcdWMxMWMgRVx1YmM4OCBcdWM4MTVcdWI5NThcdWM3YTVcdWFlNGNcdWM5YzAgXHVhYzAwXHViODI0XHViMjk0IFx1YWNlMFx1YWMxZFx1Yzc3NCBNXHViYTg1IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWM3NThcdWJiZjhcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIyZjVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD4xXHViYzg4IFx1YzgxNVx1Yjk1OFx1YzdhNVx1YzVkMFx1YzExYyAzXHViYzg4IFx1YzgxNVx1Yjk1OFx1YzdhNVx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhY2UwXHVhYzFkXHVjNzQ0IFx1YjQ1MCBcdWJhODUgXHVkMGRjXHVjNmI0XHViMmU0LiAyXHViYzg4IFx1YzgxNVx1Yjk1OFx1YzdhNVx1YzVkMFx1YzExY1x1YjI5NCA4XHViYzg4IFx1YzgxNVx1Yjk1OFx1YzdhNVx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhY2UwXHVhYzFkXHVjNzQ0IFx1ZDU1YyBcdWJhODUgXHVkMGRjXHVjNmI0XHViMmU0KFx1YzEzOCBcdWJhODVcdWM3NDQgXHViMmU0IFx1ZDBkY1x1YzZiOCBcdWQ1NDRcdWM2OTRcdWIyOTQgXHVjNWM2XHViMmU0KS4gM1x1YmM4OCBcdWM4MTVcdWI5NThcdWM3YTVcdWM1ZDBcdWMxMWMgXHViNDUwIFx1YmE4NVx1Yzc1OCBcdWFjZTBcdWFjMWRcdWM3NDQgXHViMGI0XHViODI0IFx1YzhmY1x1YWNlMCwgNFx1YmM4OCBcdWM4MTVcdWI5NThcdWM3YTVcdWM1ZDBcdWMxMWNcdWIyOTQgN1x1YmM4OCBcdWM4MTVcdWI5NThcdWM3YTVcdWM3M2NcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWNlMFx1YWMxZFx1Yzc0NCBcdWQ1NWMgXHViYTg1IFx1ZDBkY1x1YzZiNFx1YjJlNC4gN1x1YmM4OCBcdWM4MTVcdWI5NThcdWM3YTVcdWM1ZDBcdWMxMWMgXHVkNTVjIFx1YmE4NVx1Yzc1OCBcdWFjZTBcdWFjMWRcdWM3NDQgXHViMGI0XHViODI0IFx1YzhmY1x1YWNlMCwgOFx1YmM4OCBcdWM4MTVcdWI5NThcdWM3YTVcdWM1ZDBcdWMxMWMgXHViMGE4XHVjNzQwIFx1ZDU1YyBcdWJhODVcdWM3NTggXHVhY2UwXHVhYzFkXHVjNzQ0IFx1YjBiNFx1YjgyNCBcdWM5MDAgXHViNGE0LCAzXHViYzg4IFx1YzgxNVx1Yjk1OFx1YzdhNVx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhY2UwXHVhYzFkXHVjNzQ0IFx1YjQ1MCBcdWJhODUgXHVkMGRjXHVjNmI0XHViMmU0LiBcdWM3NzQgXHVhY2UwXHVhYzFkXHViNGU0XHVjNzQ0IDNcdWJjODggXHVjODE1XHViOTU4XHVjN2E1XHVjNWQwIFx1YjBiNFx1YjgyNCBcdWM4ZmNcdWFjZTAsIFx1YjJlNFx1YzJkYyAxXHViYzg4IFx1YzgxNVx1Yjk1OFx1YzdhNVx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMTk4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmx5aW5nIFJpZ2h0IiwiZGVzY3JpcHRpb24iOiI8cD5GaWd1cmluZyB0aGF0IHRoZXkgY2Fubm90IGRvIHdvcnNlIHRoYW4gdGhlIGh1bWFucyBoYXZlLCBGYXJtZXIgSm9obiYjMzk7cyBjb3dzIGhhdmUgZGVjaWRlZCB0byBzdGFydCBhbiBhaXJsaW5lLiBCZWluZyBjb3dzLCB0aGV5IGRlY2lkZSB0byBjYXRlciB0byB0aGUgaGVyZXRvZm9yZS11bnRhcHBlZCBtYXJrZXQgb2YgY293cyBhcyBwYXNzZW5nZXJzLiBUaGV5IHBsYW4gdG8gc2VydmUgdGhlIGNvd3Mgd2hvIGxpdmUgYWxvbmcgdGhlIHdlc3Rlcm4gY29hc3Qgb2YgTGFrZSBNaWNoaWdhbi4gRWFjaCBtb3JuaW5nLCB0aGV5IHdpbGwgZmx5IGZyb20gdGhlIG5vcnRoZXJuLW1vc3QgcG9pbnQgb2YgdGhlIGNvYXN0IHNvdXRod2FyZCB0b3dhcmRzIENoaWNvd2dvLCBtYWtpbmcgbWFueSBzdG9wcyBhbG9uZyB0aGUgd2F5LiBFYWNoIGV2ZW5pbmcsIHRoZXkgd2lsbCBmbHkgYmFjayBub3J0aCB0byB0aGUgbm9ydGhlcm4tbW9zdCBwb2ludC48XC9wPlxyXG5cclxuPHA+VGhleSBuZWVkIHlvdXIgaGVscCB0byBkZWNpZGUgd2hpY2ggcGFzc2VuZ2VycyB0byBjYXJyeSBlYWNoIGRheS4gRWFjaCBvZiBOICgxICZsdDs9IE4gJmx0Oz0gMTAsMDAwKSBmYXJtcyBudW1iZXJlZCAxLi5OIGFsb25nIHRoZSBjb2FzdCBjb250YWlucyBhbiBhaXJwb3J0IChGYXJtIDEgaXMgbm9ydGhlcm4tbW9zdDsgZmFybSBOIGlzIHNvdXRoZXJuLW1vc3QpLiBPbiB0aGlzIGRheSwgSyAoMSAmbHQ7PSBLICZsdDs9IDUwLDAwMCkgZ3JvdXBzIG9mIGNvd3Mgd2lzaCB0byB0cmF2ZWwuRWFjaCBncm91cCBvZiBjb3dzIHdhbnRzIHRvIGZseSBmcm9tIGEgcGFydGljdWxhciBmYXJtIHRvIGFub3RoZXIgcGFydGljdWxhciBmYXJtLiBUaGUgYWlybGluZSwgaWYgaXQgd2lzaGVzLCBpcyBhbGxvd2VkIHRvIHN0b3AgYW5kIHBpY2sgdXAgb25seSBwYXJ0IG9mIGEgZ3JvdXAuIENvd3MgdGhhdCBzdGFydCBhIGZsaWdodCwgaG93ZXZlcixtdXN0IHN0YXkgb24gdGhlIHBsYW5lIHVudGlsIHRoZXkgcmVhY2ggdGhlaXIgZGVzdGluYXRpb24uPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBjYXBhY2l0eSBDICgxICZsdDs9IEMgJmx0Oz0gMTAwKSBvZiB0aGUgYWlycGxhbmUgYW5kIHRoZSBncm91cHMgb2YgY293cyB0aGF0IHdhbnQgdG8gdHJhdmVsLCBkZXRlcm1pbmUgdGhlIG1heGltdW0gbnVtYmVyIG9mIGNvd3MgdGhhdCB0aGUgYWlybGluZSBjYW4gZmx5IHRvIHRoZWlyIGRlc3RpbmF0aW9uLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogSywgTiwgYW5kIEM8XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uSysxOiBFYWNoIGxpbmUgY29udGFpbnMgdGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIFMsIEUsIGFuZCBNIHRoYXQgc3BlY2lmeSBhIGdyb3VwIG9mIGNvd3MgdGhhdCB3aXNoZXMgdG8gdHJhdmVsLiBUaGUgTSAoMSAmbHQ7PSBNICZsdDs9IEMpIGNvd3MgYXJlIGN1cnJlbnRseSBhdCBmYXJtIFMgYW5kIHdhbnQgdG8gdHJhdmVsIHRvIGZhcm0gRSAoUyAhPSBFKS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaGUgbWF4aW11bSBudW1iZXIgb2YgY293cyB0aGF0IGNhbiBiZSBmbG93biB0byB0aGVpciBkZXN0aW5hdGlvbi4gVGhpcyBpcyB0aGUgc3VtIG9mIHRoZSBudW1iZXIgb2YgY293cyBmbG93biB0byB0aGVpciBkZXN0aW5hdGlvbiBvbiB0aGUgZmxpZ2h0IHNvdXRod2FyZCBpbiB0aGUgbW9ybmluZyBwbHVzIHRoZSBudW1iZXIgb2YgY293cyBmbG93biB0byB0aGVpciBkZXN0aW5hdGlvbiBvbiB0aGUgZmxpZ2h0IG5vcnRod2FyZCBpbiB0aGUgZXZlbmluZy48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiI8cD5Gb3VyIGdyb3VwcyBvZiBjb3dzLCBlaWdodCBmYXJtcywgYW5kIHRocmVlIHNlYXRzIG9uIHRoZSBwbGFuZS48XC9wPlxyXG5cclxuPHA+SW4gdGhlIG1vcm5pbmcsIHRoZSBmbGlnaHQgdGFrZXMgMiBjb3dzIGZyb20gMS0mZ3Q7MywgMSBjb3cgZnJvbSAyLSZndDs4LGFuZCAxIGNvdyBmcm9tIDQtJmd0OzcuIEluIHRoZSBldmVuaW5nLCB0aGUgZmxpZ2h0IHRha2VzIDIgY293cyBmcm9tIDgtJmd0OzMuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2005-2006 Season > USACO October 2005 Contest > Gold ?번

  • 문제의 오타를 찾은 사람: baek1134