{"raw_statement":[{"iden":"problem statement","content":"There is a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the edges are numbered $1$ through $M$. Edge $i$ connects Vertex $U_i$ and $V_i$. Also, Vertex $i$ has two predetermined integers $A_i$ and $B_i$. You will play the following game on this graph.\nFirst, choose one vertex and stand on it, with $W$ yen (the currency of Japan) in your pocket. Here, $A_s \\leq W$ must hold, where $s$ is the vertex you choose. Then, perform the following two kinds of operations any number of times in any order:\n\n*   Choose one vertex $v$ that is directly connected by an edge to the vertex you are standing on, and move to vertex $v$. Here, you need to have at least $A_v$ yen in your pocket when you perform this move.\n*   Donate $B_v$ yen to the vertex $v$ you are standing on. Here, the amount of money in your pocket must not become less than $0$ yen.\n\nYou win the game when you donate once to every vertex. Find the smallest initial amount of money $W$ that enables you to win the game."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^5$\n*   $N-1 \\leq M \\leq 10^5$\n*   $1 \\leq A_i,B_i \\leq 10^9$\n*   $1 \\leq U_i < V_i \\leq N$\n*   The given graph is connected and simple (there is at most one edge between any pair of vertices)."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$:$\n$A_N$ $B_N$\n$U_1$ $V_1$\n$U_2$ $V_2$\n$:$\n$U_M$ $V_M$"},{"iden":"sample input 1","content":"4 5\n3 1\n1 2\n4 1\n6 2\n1 2\n2 3\n2 4\n1 4\n3 4"},{"iden":"sample output 1","content":"6\n\nIf you have $6$ yen initially, you can win the game as follows:\n\n*   Stand on Vertex $4$. This is possible since you have not less than $6$ yen.\n*   Donate $2$ yen to Vertex $4$. Now you have $4$ yen.\n*   Move to Vertex $3$. This is possible since you have not less than $4$ yen.\n*   Donate $1$ yen to Vertex $3$. Now you have $3$ yen.\n*   Move to Vertex $2$. This is possible since you have not less than $1$ yen.\n*   Move to Vertex $1$. This is possible since you have not less than $3$ yen.\n*   Donate $1$ yen to Vertex $1$. Now you have $2$ yen.\n*   Move to Vertex $2$. This is possible since you have not less than $1$ yen.\n*   Donate $2$ yen to Vertex $2$. Now you have $0$ yen.\n\nIf you have less than $6$ yen initially, you cannot win the game. Thus, the answer is $6$."},{"iden":"sample input 2","content":"5 8\n6 4\n15 13\n15 19\n15 1\n20 7\n1 3\n1 4\n1 5\n2 3\n2 4\n2 5\n3 5\n4 5"},{"iden":"sample output 2","content":"44"},{"iden":"sample input 3","content":"9 10\n131 2\n98 79\n242 32\n231 38\n382 82\n224 22\n140 88\n209 70\n164 64\n6 8\n1 6\n1 4\n1 3\n4 7\n4 9\n3 7\n3 9\n5 9\n2 5"},{"iden":"sample output 3","content":"582"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}