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

문제

학생들은 선생님들과 조교들이 스타를 하러 간 사이에 여러 방에 들어가 신나게 놀고 있었다. 그리고 시간이 되어 놀던 방에서 자려고 했지만 각 방에서 잘 수 있는 사람의 수가 정해져 있어서 불가피하게 몇몇 학생들은 방을 옮겨 자야한다. 하지만 학생들이 옮기는 시간 중에 스타를 끝내고 오신 원장선생님과 마주치게 되면 안되기 때문에 고민에 빠져있다. 결국 최대한 빠른 시간에 모든 학생들이 방에 잘 수 있는 제한 수를 넘지 않으면서 적당한 방에 숨어 자려고 한다.

F개의 방에 학생들이 현재 숨어 있고, 이 방들을 연결하는 P개의 통로가 있다. 통로의 폭은 넓기 때문에 동시에 한 통로에 지나가는 학생 수의 제한은 없고 양방으로 통행 가능하다.

모든 방의 제한이 넘지 않도록 학생들이 이동해야 하는 최소 시간을 출력하는 것이 문제이다. 물론 몇몇 학생들은 현재 방에 있을 수 있다. (근데, 아마 이 시간보다 스타가 빨리 끝날듯..)

입력

첫 번째 줄에 F(1≤F≤200), P(1≤P≤1,500)가 주어진다. 2번째 줄부터 F개의 줄까지 i번째 줄에는 i-1번째 방에 현재 있는 학생 수와 그 방에 잘 수 있는 학생 수가 빈칸으로 구분되어 주어진다. 두 수 모두 0 이상 1000 이하의 수이다. 다음 P개의 줄에는 한 통로가 연결되는 두 방과 그 통로를 통과하는데 걸리는 시간(≤1,000,000,000)이 주어진다.

출력

학생들이 이동해야 하는 최소 시간을 출력한다. 불가능할 경우 -1을 출력한다.

예제 입력 1

3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120

예제 출력 1

110

힌트

1번 방에 있는 학생 중 2명은 이 방에 남고 4명은 2번 방에 이동하며, 남은 1명은 3번 방으로 가면 총 110의 시간이 소요된다.

W3sicHJvYmxlbV9pZCI6IjE3NDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMjhcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWMxMjBcdWMwZGRcdWIyZDhcdWI0ZTRcdWFjZmMgXHVjODcwXHVhZDUwXHViNGU0XHVjNzc0IFx1YzJhNFx1ZDBjMFx1Yjk3YyBcdWQ1NThcdWI3ZWMgXHVhYzA0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWM1ZWNcdWI3ZWMgXHViYzI5XHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwMCBcdWMyZTBcdWIwOThcdWFjOGMgXHViMTgwXHVhY2UwIFx1Yzc4OFx1YzVjOFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWI0MThcdWM1YjQgXHViMTgwXHViMzU4IFx1YmMyOVx1YzVkMFx1YzExYyBcdWM3OTBcdWI4MjRcdWFjZTAgXHVkNTg4XHVjOWMwXHViOWNjIFx1YWMwMSBcdWJjMjlcdWM1ZDBcdWMxMWMgXHVjNzk4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4MTVcdWQ1NzRcdWM4MzggXHVjNzg4XHVjNWI0XHVjMTFjIFx1YmQ4OFx1YWMwMFx1ZDUzY1x1ZDU1OFx1YWM4YyBcdWJhODdcdWJhODcgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YmMyOVx1Yzc0NCBcdWM2MmVcdWFjYTggXHVjNzkwXHVjNTdjXHVkNTVjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YzYyZVx1YWUzMFx1YjI5NCBcdWMyZGNcdWFjMDQgXHVjOTExXHVjNWQwIFx1YzJhNFx1ZDBjMFx1Yjk3YyBcdWIwNWRcdWIwYjRcdWFjZTAgXHVjNjI0XHVjMmUwIFx1YzZkMFx1YzdhNVx1YzEyMFx1YzBkZFx1YjJkOFx1YWNmYyBcdWI5YzhcdWM4ZmNcdWNlNThcdWFjOGMgXHViNDE4XHViYTc0IFx1YzU0OFx1YjQxOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVhY2UwXHViYmZjXHVjNWQwIFx1YmU2MFx1YzgzOFx1Yzc4OFx1YjJlNC4gXHVhY2IwXHVhZDZkIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0XHVjNWQwICBcdWJhYThcdWI0ZTAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YmMyOVx1YzVkMCBcdWM3OTggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MWNcdWQ1NWMgXHVjMjE4XHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzRcdWMxMWMgXHVjODAxXHViMmY5XHVkNTVjIFx1YmMyOVx1YzVkMCBcdWMyMjhcdWM1YjQgXHVjNzkwXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gIDxcL3A+XHJcblxyXG48cD5GXHVhYzFjXHVjNzU4IFx1YmMyOVx1YzVkMCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQgXHVkNjA0XHVjN2FjIFx1YzIyOFx1YzViNCBcdWM3ODhcdWFjZTAsIFx1Yzc3NCBcdWJjMjlcdWI0ZTRcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFBcdWFjMWNcdWM3NTggXHVkMWI1XHViODVjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVkMWI1XHViODVjXHVjNzU4IFx1ZDNlZFx1Yzc0MCBcdWIxMTNcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YjNkOVx1YzJkY1x1YzVkMCBcdWQ1NWMgXHVkMWI1XHViODVjXHVjNWQwIFx1YzljMFx1YjA5OFx1YWMwMFx1YjI5NCBcdWQ1NTlcdWMwZGQgXHVjMjE4XHVjNzU4IFx1YzgxY1x1ZDU1Y1x1Yzc0MCBcdWM1YzZcdWFjZTAgXHVjNTkxXHViYzI5XHVjNzNjXHViODVjIFx1ZDFiNVx1ZDU4OSBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWJjMjlcdWM3NTggXHVjODFjXHVkNTVjXHVjNzc0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIzYzRcdWI4NWQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1Yzc3NFx1YjNkOVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmIzOFx1YzgxY1x1Yzc3NFx1YjJlNC4gXHViYjNjXHViODYwIFx1YmE4N1x1YmE4NyBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVkNjA0XHVjN2FjIFx1YmMyOVx1YzVkMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKFx1YWRmY1x1YjM3MCwgXHVjNTQ0XHViOWM4IFx1Yzc3NCBcdWMyZGNcdWFjMDRcdWJjZjRcdWIyZTQgXHVjMmE0XHVkMGMwXHVhYzAwIFx1YmU2OFx1YjlhYyBcdWIwNWRcdWIwYTBcdWI0ZWYuLik8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIEYoMSZsZTtGJmxlOzIwMCksIFAoMSZsZTtQJmxlOzEsNTAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIDJcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIEZcdWFjMWNcdWM3NTggXHVjOTA0XHVhZTRjXHVjOWMwIGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IGktMVx1YmM4OFx1YzlmOCBcdWJjMjlcdWM1ZDAgXHVkNjA0XHVjN2FjIFx1Yzc4OFx1YjI5NCBcdWQ1NTlcdWMwZGQgXHVjMjE4XHVjNjQwIFx1YWRmOCBcdWJjMjlcdWM1ZDAgXHVjNzk4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkNTU5XHVjMGRkIFx1YzIxOFx1YWMwMCBcdWJlNDhcdWNlNzhcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YzIxOCBcdWJhYThcdWI0NTAgMCBcdWM3NzRcdWMwYzEgMTAwMCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjMjE4XHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGMgUFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTVjIFx1ZDFiNVx1Yjg1Y1x1YWMwMCBcdWM1ZjBcdWFjYjBcdWI0MThcdWIyOTQgXHViNDUwIFx1YmMyOVx1YWNmYyBcdWFkZjggXHVkMWI1XHViODVjXHViOTdjIFx1ZDFiNVx1YWNmY1x1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0KCZsZTsxLDAwMCwwMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1Yzc3NFx1YjNkOVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU2MCBcdWFjYmRcdWM2YjAgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD4xXHViYzg4IFx1YmMyOVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVkNTU5XHVjMGRkIFx1YzkxMSAyXHViYTg1XHVjNzQwIFx1Yzc3NCBcdWJjMjlcdWM1ZDAgXHViMGE4XHVhY2UwIDRcdWJhODVcdWM3NDAgMlx1YmM4OCBcdWJjMjlcdWM1ZDAgXHVjNzc0XHViM2Q5XHVkNTU4XHViYTcwLCBcdWIwYThcdWM3NDAgMVx1YmE4NVx1Yzc0MCAzXHViYzg4IFx1YmMyOVx1YzczY1x1Yjg1YyBcdWFjMDBcdWJhNzQgXHVjZDFkIDExMFx1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVjMThjXHVjNjk0XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTc0NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik9tYnJvcGhvYmljIEJvdmluZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkZKJiMzOTtzIGNvd3MgcmVhbGx5IGhhdGUgZ2V0dGluZyB3ZXQgc28gbXVjaCB0aGF0IHRoZSBtZXJlIHRob3VnaHQgb2YgZ2V0dGluZyBjYXVnaHQgaW4gdGhlIHJhaW4gbWFrZXMgdGhlbSBzaGFrZSBpbiB0aGVpciBob292ZXMuIFRoZXkgaGF2ZSBkZWNpZGVkIHRvIHB1dCBhIHJhaW4gc2lyZW4gb24gdGhlIGZhcm0gdG8gbGV0IHRoZW0ga25vdyB3aGVuIHJhaW4gaXMgYXBwcm9hY2hpbmcuIFRoZXkgaW50ZW5kIHRvIGNyZWF0ZSBhIHJhaW4gZXZhY3VhdGlvbiBwbGFuIHNvIHRoYXQgYWxsIHRoZSBjb3dzIGNhbiBnZXQgdG8gc2hlbHRlciBiZWZvcmUgdGhlIHJhaW4gYmVnaW5zLiBXZWF0aGVyIGZvcmVjYXN0aW5nIGlzIG5vdCBhbHdheXMgY29ycmVjdCwgdGhvdWdoLiBJbiBvcmRlciB0byBtaW5pbWl6ZSBmYWxzZSBhbGFybXMsIHRoZXkgd2FudCB0byBzb3VuZCB0aGUgc2lyZW4gYXMgbGF0ZSBhcyBwb3NzaWJsZSB3aGlsZSBzdGlsbCBnaXZpbmcgZW5vdWdoIHRpbWUgZm9yIGFsbCB0aGUgY293cyB0byBnZXQgdG8gc29tZSBzaGVsdGVyLjxcL3A+XHJcblxyXG48cD5UaGUgZmFybSBoYXMgRiAoMSAmbHQ7PSBGICZsdDs9IDIwMCkgZmllbGRzIG9uIHdoaWNoIHRoZSBjb3dzIGdyYXplLiBBIHNldCBvZiBQICgxICZsdDs9IFAgJmx0Oz0gMTUwMCkgcGF0aHMgY29ubmVjdHMgdGhlbS4gVGhlIHBhdGhzIGFyZSB3aWRlLCBzbyB0aGF0IGFueSBudW1iZXIgb2YgY293cyBjYW4gdHJhdmVyc2UgYSBwYXRoIGluIGVpdGhlciBkaXJlY3Rpb24uPFwvcD5cclxuXHJcbjxwPlNvbWUgb2YgdGhlIGZhcm0mIzM5O3MgZmllbGRzIGhhdmUgcmFpbiBzaGVsdGVycyB1bmRlciB3aGljaCB0aGUgY293cyBjYW4gc2hpZWxkIHRoZW1zZWx2ZXMuIFRoZXNlIHNoZWx0ZXJzIGFyZSBvZiBsaW1pdGVkIHNpemUsIHNvIGEgc2luZ2xlIHNoZWx0ZXIgbWlnaHQgbm90IGJlIGFibGUgdG8gaG9sZCBhbGwgdGhlIGNvd3MuIEZpZWxkcyBhcmUgc21hbGwgY29tcGFyZWQgdG8gdGhlIHBhdGhzIGFuZCByZXF1aXJlIG5vIHRpbWUgZm9yIGNvd3MgdG8gdHJhdmVyc2UuPFwvcD5cclxuXHJcbjxwPkNvbXB1dGUgdGhlIG1pbmltdW0gYW1vdW50IG9mIHRpbWUgYmVmb3JlIHJhaW4gc3RhcnRzIHRoYXQgdGhlIHNpcmVuIG11c3QgYmUgc291bmRlZCBzbyB0aGF0IGV2ZXJ5IGNvdyBjYW4gZ2V0IHRvIHNvbWUgc2hlbHRlci48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBGIGFuZCBQPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLkYrMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyB0aGF0IGRlc2NyaWJlIGEgZmllbGQuIFRoZSBmaXJzdCBpbnRlZ2VyIChyYW5nZTogMC4uMTAwMCkgaXMgdGhlIG51bWJlciBvZiBjb3dzIGluIHRoYXQgZmllbGQuIFRoZSBzZWNvbmQgaW50ZWdlciAocmFuZ2U6IDAuLjEwMDApIGlzIHRoZSBudW1iZXIgb2YgY293cyB0aGUgc2hlbHRlciBpbiB0aGF0IGZpZWxkIGNhbiBob2xkLiBMaW5lIGkrMSBkZXNjcmliZXMgZmllbGQgaS48XC9saT5cclxuXHQ8bGk+TGluZXMgRisyLi5GK1ArMTogVGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIHRoYXQgZGVzY3JpYmUgYSBwYXRoLiBUaGUgZmlyc3QgYW5kIHNlY29uZCBpbnRlZ2VycyAoYm90aCByYW5nZSAxLi5GKSB0ZWxsIHRoZSBmaWVsZHMgY29ubmVjdGVkIGJ5IHRoZSBwYXRoLiBUaGUgdGhpcmQgaW50ZWdlciAocmFuZ2U6IDEuLjEsMDAwLDAwMCwwMDApIGlzIGhvdyBsb25nIGFueSBjb3cgdGFrZXMgdG8gdHJhdmVyc2UgaXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVGhlIG1pbmltdW0gYW1vdW50IG9mIHRpbWUgcmVxdWlyZWQgZm9yIGFsbCBjb3dzIHRvIGdldCB1bmRlciBhIHNoZWx0ZXIsIHByZXN1bWluZyB0aGV5IHBsYW4gdGhlaXIgcm91dGVzIG9wdGltYWxseS4gSWYgaXQgbm90IHBvc3NpYmxlIGZvciB0aGUgYWxsIHRoZSBjb3dzIHRvIGdldCB1bmRlciBhIHNoZWx0ZXIsIG91dHB1dCAmcXVvdDstMSZxdW90Oy48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiI8cD5JbiAxMTAgdGltZSB1bml0cywgdHdvIGNvd3MgZnJvbSBmaWVsZCAxIGNhbiBnZXQgdW5kZXIgdGhlIHNoZWx0ZXIgaW4gdGhhdCBmaWVsZCwgZm91ciBjb3dzIGZyb20gZmllbGQgMSBjYW4gZ2V0IHVuZGVyIHRoZSBzaGVsdGVyIGluIGZpZWxkIDIsIGFuZCBvbmUgY293IGNhbiBnZXQgdG8gZmllbGQgMyBhbmQgam9pbiB0aGUgY293cyBmcm9tIHRoYXQgZmllbGQgdW5kZXIgdGhlIHNoZWx0ZXIgaW4gZmllbGQgMy4gQWx0aG91Z2ggdGhlcmUgYXJlIG90aGVyIHBsYW5zIHRoYXQgd2lsbCBnZXQgYWxsIHRoZSBjb3dzIHVuZGVyIGEgc2hlbHRlciwgbm9uZSB3aWxsIGRvIGl0IGluIGZld2VyIHRoYW4gMTEwIHRpbWUgdW5pdHMuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2004-2005 Season > USACO March 2005 Contest > Gold 1번

  • 문제를 번역한 사람: author6