시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 39 23 14 60.870%

문제

포천 주민들은 여러 버스 정류장에서 버스를 기다리고 있다. 하지만 안타깝게도 버스는 이 모든 사람들을 수용할 수 있는 크기가 되지 못한다. 

문제는 정류장의 개수 N과 M개의 그룹에 대해 현재 기다리는 정류장 번호와 내릴 정류장 번호가 주어지면 1번 정류장에서 출발하여 N번 정류장까지 운행할 때 최대 태울 수 있는 인원을 구하는 것이다. 단, 버스는 1, 2, …, N번 정류장 순서로 방문한다.

입력

첫 줄에는 그룹의 수 K(1 ≤ K ≤ 50,000)와 정류장 개수 N(1 ≤ N ≤ 20,000)과 버스의 최대 수용 인원 C(1 ≤ C ≤ 100)가 공백으로 구분되어 주어진다. 두 번째 줄부터 K+1번째 줄까지 각 줄에 대해 K개의 그룹에 대한 정보가 담긴 Si, Ei, Mi가 주어지는데 이는 이 그룹은 총 Mi명이고 Si번 정류장에서 출발하여 Ei번 정류장에서 내릴려고 한다는 의미이다.

출력

첫 줄에 최대 수송 인원을 출력한다.

예제 입력 1

8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1

예제 출력 1

10

힌트

버스가 1번->5번으로 가는 2명인 그룹과 5번->8번으로 가는 3명인 그룹, 8번->14번으로 가는 2명인 그룹, 9번->12번으로 가는 1명인 그룹, 13번->14번으로 가는 1명인 그룹, 14번->15번으로 가는 1명인 그룹을 태우면 총 10명을 수송한 셈이 된다.

W3sicHJvYmxlbV9pZCI6IjExNjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjODRcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDNlY1x1Y2M5YyBcdWM4ZmNcdWJiZmNcdWI0ZTRcdWM3NDAgXHVjNWVjXHViN2VjIFx1YmM4NFx1YzJhNCBcdWM4MTVcdWI5NThcdWM3YTVcdWM1ZDBcdWMxMWMgXHViYzg0XHVjMmE0XHViOTdjIFx1YWUzMFx1YjJlNFx1YjlhY1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWM1NDhcdWQwYzBcdWFlNWRcdWFjOGNcdWIzYzQgXHViYzg0XHVjMmE0XHViMjk0IFx1Yzc3NCBcdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzQ0IFx1YzIxOFx1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWI0MThcdWM5YzAgXHViYWJiXHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWIyOTQgXHVjODE1XHViOTU4XHVjN2E1XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVhY2ZjIE1cdWFjMWNcdWM3NTggXHVhZGY4XHViOGY5XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWQ2MDRcdWM3YWMgXHVhZTMwXHViMmU0XHViOWFjXHViMjk0IFx1YzgxNVx1Yjk1OFx1YzdhNSBcdWJjODhcdWQ2MzhcdWM2NDAgXHViMGI0XHViOWI0IFx1YzgxNVx1Yjk1OFx1YzdhNSBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTc0IDFcdWJjODggXHVjODE1XHViOTU4XHVjN2E1XHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU1OFx1YzVlYyBOXHViYzg4IFx1YzgxNVx1Yjk1OFx1YzdhNVx1YWU0Y1x1YzljMCBcdWM2YjRcdWQ1ODlcdWQ1NjAgXHViNTRjIFx1Y2Q1Y1x1YjMwMCBcdWQwZGNcdWM2YjggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM3NzhcdWM2ZDBcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViMmU4LCBcdWJjODRcdWMyYTRcdWIyOTQgMSwgMiwgJmhlbGxpcDssIE5cdWJjODggXHVjODE1XHViOTU4XHVjN2E1IFx1YzIxY1x1YzExY1x1Yjg1YyBcdWJjMjlcdWJiMzhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWRmOFx1YjhmOVx1Yzc1OCBcdWMyMTggSygxICZsZTsgSyAmbGU7IDUwLDAwMClcdWM2NDAgXHVjODE1XHViOTU4XHVjN2E1IFx1YWMxY1x1YzIxOCBOKDEgJmxlOyBOICZsZTsgMjAsMDAwKVx1YWNmYyBcdWJjODRcdWMyYTRcdWM3NTggXHVjZDVjXHViMzAwIFx1YzIxOFx1YzZhOSBcdWM3NzhcdWM2ZDAgQygxICZsZTsgQyAmbGU7IDEwMClcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIEsrMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAgXHVhYzAxIFx1YzkwNFx1YzVkMCBcdWIzMDBcdWQ1NzQgS1x1YWMxY1x1Yzc1OCBcdWFkZjhcdWI4ZjlcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWIyZjRcdWFlMzQgU2ksIEVpLCBNaVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAgXHVjNzc0XHViMjk0IFx1Yzc3NCBcdWFkZjhcdWI4ZjlcdWM3NDAgXHVjZDFkIE1pXHViYTg1XHVjNzc0XHVhY2UwIFNpXHViYzg4IFx1YzgxNVx1Yjk1OFx1YzdhNVx1YzVkMFx1YzExYyBcdWNkOWNcdWJjMWNcdWQ1NThcdWM1ZWMgRWlcdWJjODggXHVjODE1XHViOTU4XHVjN2E1XHVjNWQwXHVjMTFjIFx1YjBiNFx1YjliNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTRcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjZDVjXHViMzAwIFx1YzIxOFx1YzFhMSBcdWM3NzhcdWM2ZDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWJjODRcdWMyYTRcdWFjMDAgMVx1YmM4OC0mZ3Q7NVx1YmM4OFx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgMlx1YmE4NVx1Yzc3OCBcdWFkZjhcdWI4ZjlcdWFjZmMgNVx1YmM4OC0mZ3Q7OFx1YmM4OFx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgM1x1YmE4NVx1Yzc3OCBcdWFkZjhcdWI4ZjksIDhcdWJjODgtJmd0OzE0XHViYzg4XHVjNzNjXHViODVjIFx1YWMwMFx1YjI5NCAyXHViYTg1XHVjNzc4IFx1YWRmOFx1YjhmOSwgOVx1YmM4OC0mZ3Q7MTJcdWJjODhcdWM3M2NcdWI4NWMgXHVhYzAwXHViMjk0IDFcdWJhODVcdWM3NzggXHVhZGY4XHViOGY5LCAxM1x1YmM4OC0mZ3Q7MTRcdWJjODhcdWM3M2NcdWI4NWMgXHVhYzAwXHViMjk0IDFcdWJhODVcdWM3NzggXHVhZGY4XHViOGY5LCAxNFx1YmM4OC0mZ3Q7MTVcdWJjODhcdWM3M2NcdWI4NWMgXHVhYzAwXHViMjk0IDFcdWJhODVcdWM3NzggXHVhZGY4XHViOGY5XHVjNzQ0IFx1ZDBkY1x1YzZiMFx1YmE3NCBcdWNkMWQgMTBcdWJhODVcdWM3NDQgXHVjMjE4XHVjMWExXHVkNTVjIFx1YzE0OFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTYxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmFpciBTaHV0dGxlIiwiZGVzY3JpcHRpb24iOiI8cD5BbHRob3VnaCBGYXJtZXIgSm9obiBoYXMgbm8gcHJvYmxlbXMgd2Fsa2luZyBhcm91bmQgdGhlIGZhaXIgdG8gY29sbGVjdCBwcml6ZXMgb3Igc2VlIHRoZSBzaG93cywgaGlzIGNvd3MgYXJlIG5vdCBpbiBzdWNoIGdvb2Qgc2hhcGU7IGEgZnVsbCBkYXkgb2Ygd2Fsa2luZyBhcm91bmQgdGhlIGZhaXIgbGVhdmVzIHRoZW0gZXhoYXVzdGVkLiBUbyBoZWxwIHRoZW0gZW5qb3kgdGhlIGZhaXIsIEZKIGhhcyBhcnJhbmdlZCBmb3IgYSBzaHV0dGxlIHRydWNrIHRvIHRha2UgdGhlIGNvd3MgZnJvbSBwbGFjZSB0byBwbGFjZSBpbiB0aGUgZmFpcmdyb3VuZHMuPFwvcD5cclxuXHJcbjxwPkZKIGNvdWxkbiYjMzk7dCBhZmZvcmQgYSByZWFsbHkgZ3JlYXQgc2h1dHRsZSwgc28gdGhlIHNodXR0bGUgaGUgcmVudGVkIHRyYXZlcnNlcyBpdHMgcm91dGUgb25seSBvbmNlICghKSBhbmQgbWFrZXMgTiAoMSAmbHQ7PSBOICZsdDs9IDIwLDAwMCkgc3RvcHMgKGNvbnZlbmllbnRseSBudW1iZXJlZCAxLi5OKSBhbG9uZyBpdHMgcGF0aC4gQSB0b3RhbCBvZiBLICgxICZsdDs9IEsgJmx0Oz0gNTAsMDAwKSBncm91cHMgb2YgY293cyBjb252ZW5pZW50bHkgbnVtYmVyZWQgMS4uSyB3aXNoIHRvIHVzZSB0aGUgc2h1dHRsZSwgZWFjaCBvZiB0aGUgTV9pICgxICZsdDs9IE1faSAmbHQ7PSBOKSBjb3dzIGluIGdyb3VwIGkgd2FudGluZyB0byByaWRlIGZyb20gb25lIHN0b3AgU19pICgxICZsdDs9IFNfaSAmbHQ7IEVfaSkgdG8gYW5vdGhlciBzdG9wIEVfaSAoU19pICZsdDsgRV9pICZsdDs9IE4pIGZhcnRoZXIgYWxvbmcgdGhlIHJvdXRlLjxcL3A+XHJcblxyXG48cD5UaGUgc2h1dHRsZSBtaWdodCBub3QgYmUgYWJsZSB0byBwaWNrIHVwIGFuIGVudGlyZSBncm91cCBvZiBjb3dzIChzaW5jZSBpdCBoYXMgbGltaXRlZCBjYXBhY2l0eSkgYnV0IGNhbiBwaWNrIHVwIHBhcnRpYWwgZ3JvdXBzIGFzIGFwcHJvcHJpYXRlLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgY2FwYWNpdHkgQyAoMSAmbHQ7PSBDICZsdDs9IDEwMCkgb2YgdGhlIHNodXR0bGUgdHJ1Y2sgYW5kIHRoZSBkZXNjcmlwdGlvbnMgb2YgdGhlIGdyb3VwcyBvZiBjb3dzIHRoYXQgd2FudCB0byB2aXNpdCB2YXJpb3VzIHNpdGVzIGF0IHRoZSBmYWlyLCBkZXRlcm1pbmUgdGhlIG1heGltdW0gbnVtYmVyIG9mIGNvd3MgdGhhdCBjYW4gcmlkZSB0aGUgc2h1dHRsZSBkdXJpbmcgdGhlIGZhaXIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogVGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBLLCBOLCBhbmQgQzxcL3A+XHJcblxyXG48cD4qIExpbmVzIDIuLksrMTogTGluZSBpKzEgZGVzY3JpYmVzIGdyb3VwIGkgb2YgdGhlIGNvd3Mgd2l0aCB0aHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IFNfaSwgRV9pLCBhbmQgTV9pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IFRoZSBtYXhpbXVtIG51bWJlciBvZiBjb3dzIHRoYXQgY2FuIHJpZGUgdGhlIHNodXR0bGUgYXQgdGhlIGZhaXIuPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBzaHV0dGxlIGNhbiB0YWtlIDIgY293cyBmcm9tIHN0b3AgMSB0byBzdG9wIDUsIDMgZnJvbSA1IHRvIDgsIDIgZnJvbSA4IHRvIDE0LCAxIGZyb20gOSB0byAxMiwgMSBmcm9tIDEzIHRvIDE0LCBhbmQgMSBmcm9tIDE0IHRvIDE1LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO February 2009 Contest > Gold 1번

  • 문제를 번역한 사람: author6
  • 문제의 오타를 찾은 사람: dotorya