숨기

여러 방에 학생들이 숨어 있다. 각 방에는 현재 머무는 학생 수와 그 방에서 잘 수 있는 최대 인원이 정해져 있다. 모든 방의 인원수가 제한을 넘지 않도록 일부 학생을 다른 방으로 옮겨야 한다.

방은 1번부터 F번까지 번호가 붙어 있고, 방 사이에는 P개의 통로가 있다. 한 통로를 동시에 지나는 학생 수에는 제한이 없으며, 모든 통로는 양방향으로 이동할 수 있다. 학생 한 명이 어떤 경로로 이동하는 데 걸리는 시간은 지나간 통로 시간의 합이다. 모든 학생은 동시에 이동할 수 있으므로, 전체 이동 시간은 이동한 학생들 중 가장 오래 걸린 시간이다.

몇몇 학생은 현재 방에 그대로 남아도 된다. 모든 방의 제한을 지키도록 학생들을 배치할 때 필요한 최소 전체 이동 시간을 구하라.

첫째 줄에 방의 수 F(1 ≤ F ≤ 200)와 통로의 수 P(1 ≤ P ≤ 1,500)가 주어진다.

다음 F개 줄에는 1번 방부터 F번 방까지 순서대로, 현재 그 방에 있는 학생 수와 그 방에서 잘 수 있는 최대 인원이 공백으로 구분되어 주어진다. 두 값은 모두 0 이상 1,000 이하의 정수이다.

다음 P개 줄에는 통로가 연결하는 두 방의 번호와 그 통로를 지나가는 데 걸리는 시간이 주어진다. 통로 시간은 1,000,000,000 이하의 정수이다.

학생들을 옮겨 모든 방의 인원 제한을 만족시키는 데 필요한 최소 전체 이동 시간을 출력한다. 불가능하면 -1을 출력한다.

1번 방에 있는 학생 중 2명은 그대로 남고, 4명은 2번 방으로 이동하며, 1명은 3번 방으로 이동하면 된다. 3번 방으로 가는 최단 경로의 시간은 110이므로 전체 이동 시간은 110이다.