문제
N개의 정점과 M개의 양방향 간선으로 이루어진 그래프가 있다. 정점은 1부터 N까지 번호가 붙어있고, 간선은 1부터 M까지 번호가 붙어있다. i번째 간선은 정점 Ui와 정점 Vi를 연결한다. 정점 i에는 정수 Ai와 Bi가 부여되어 있다. 당신은 이 그래프에서 게임을 할 것이다.
먼저, W원을 들고 정점 s를 골라 그 정점으로 간다. 여기서, As ≤ W를 만족시켜야 한다. 그 후, 당신은 다음 두 행동을 자유롭게 할 수 있다.
당신이 위치한 정점과 인접한 정점 v를 선택한 뒤, v로 움직인다. 여기서, 당신은 Av원 이상의 돈을 가지고 있어야 한다.
당신이 서 있는 정점 v에 Bv만큼의 기부를 한다. 여기서, 당신은 기부한 뒤 남은 돈이 0원 이상 있어야 한다.
당신은 모든 정점에 한 번씩 기부를 해야 게임을 이길 수 있다. 당신이 게임을 이기기 위한 최소 W를 구하여라.
입력
다음과 같은 형식으로 주어진다.
N M
A1 B1
A2 B2
AN BN
U1 V1
U2 V2
UM VM
[제한사항]
1 ≤ N ≤ 105
N-1 ≤ M ≤ 105
1 ≤ Ai, Bi ≤ 109
1 ≤ Ui < Vi ≤ N
그래프는 연결그래프이고, 중복 간선이 없다.
출력
당신이 게임을 이길 수 있는 최소 W를 출력하여라.
예제 #1
4 5
3 1
1 2
4 1
6 2
1 2
2 3
2 4
1 4
3 4
6
처음에 6원을 가지고 있는 경우, 다음과 같이 이동하면 이길 수 있다.
4번 정점에서 시작한다. 6원 이상을 가지고 있기 때문에 가능하다.
4번 정점에 2원을 기부한다. 4원이 남아있다.
3번 정점으로 이동한다. 4원 이상을 가지고 있기 때문에 가능하다.
3번 정점에 1원을 기부한다. 3원이 남아있다.
2번 정점으로 이동한다. 1원 이상을 가지고 있기 때문에 가능하다.
1번 정점으로 이동한다. 3원 이상을 가지고 있기 때문에 가능하다.
1번 정점에 1원을 기부한다. 2원이 남아있다.
2번 정점으로 이동한다. 1원 이상을 가지고 있기 때문에 가능하다.
2번 정점에 2원을 기부한다. 0원이 남아있다.
만약 6원보다 적게 가지고 시작한다면 게임을 이길 수 없다. 때문에 답은 6이다.
예제 #2
5 8
6 4
15 13
15 19
15 1
20 7
1 3
1 4
1 5
2 3
2 4
2 5
3 5
4 5
44
예제 #3
9 10
131 2
98 79
242 32
231 38
382 82
224 22
140 88
209 70
164 64
6 8
1 6
1 4
1 3
4 7
4 9
3 7
3 9
5 9
2 5
582
로그인해야 코드를 작성할 수 있어요.