시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 35 11 9 27.273%

문제

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

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

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

입력

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

출력

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

예제 입력

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

예제 출력

110

힌트

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

출처

  • 문제를 번역한 사람: author6