N개의 정점과 M개의 양방향 간선으로 이루어진 그래프가 있다. 정점은 1부터 N까지 번호가 붙어있고, 간선은 1부터 M까지 번호가 붙어있다. i번째 간선은 정점 U_i와 정점 V_i를 연결한다. 정점 i에는 정수 A_i와 B_i가 부여되어 있다. 당신은 이 그래프에서 게임을 할 것이다.

먼저, W원을 들고 정점 s를 골라 그 정점으로 간다. 여기서, A_s ≤ W를 만족시켜야 한다. 그 후, 당신은 다음 두 행동을 자유롭게 할 수 있다.

당신이 위치한 정점과 인접한 정점 v를 선택한 뒤, v로 움직인다. 여기서, 당신은 A_v원 이상의 돈을 가지고 있어야 한다.
당신이 서 있는 정점 v에 B_v만큼의 기부를 한다. 여기서, 당신은 기부한 뒤 남은 돈이 0원 이상 있어야 한다.

당신은 모든 정점에 한 번씩 기부를 해야 게임을 이길 수 있다. 당신이 게임을 이기기 위한 최소 W를 구하여라.

#3648 upload 2 done 2 how_to_reg 2

기부 timer 1s memory 256MB

#3648

기부 1s 256MB