{"raw_statement":[{"iden":"problem statement","content":"Given is a simple undirected graph with $N$ vertices and $M$ edges. Its vertices are numbered $1, 2, \\ldots, N$ and its edges are numbered $1, 2, \\ldots, M$. On Vertex $i$ ($1 \\leq i \\leq N$) two integers $A_i$ and $B_i$ are written. Edge $i$ ($1 \\leq i \\leq M$) connects Vertices $U_i$ and $V_i$.\nSnuke picks zero or more vertices and delete them. Deleting Vertex $i$ costs $A_i$. When a vertex is deleted, edges that are incident to the vertex are also deleted. The _score_ after deleting vertices is calculated as follows:\n\n*   The score is the sum of the scores of all connected components.\n*   The score of a connected component is the absolute value of the sum of $B_i$ of the vertices in the connected component.\n\nSnuke's _profit_ is $($score$)$ $-$ $($the sum of costs$)$. Find the maximum possible profit Snuke can gain."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 300$\n*   $1 \\leq M \\leq 300$\n*   $1 \\leq A_i \\leq 10^6$\n*   $-10^6 \\leq B_i \\leq 10^6$\n*   $1 \\leq U_i,V_i \\leq N$\n*   The given graph does not contain self loops or multiple edges.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n$B_1$ $B_2$ $\\cdots$ $B_N$\n$U_1$ $V_1$\n$U_2$ $V_2$\n$\\vdots$\n$U_M$ $V_M$"},{"iden":"sample input 1","content":"4 4\n4 1 2 3\n0 2 -3 1\n1 2\n2 3\n3 4\n4 2"},{"iden":"sample output 1","content":"1\n\nDeleting Vertex $2$ costs $1$. After that, the graph is separated into two connected components. The score of the component consisting of Vertex $1$ is $|0| = 0$. The score of the component consisting of Vertices $3$ and $4$ is $|(-3) + 1| = 2$. Therefore, Snuke's profit is $0 + 2 - 1 = 1$. He cannot gain more than $1$, so the answer is $1$."},{"iden":"sample input 2","content":"10 12\n733454 729489 956011 464983 822120 364691 271012 762026 751760 965431\n-817837 -880667 -822819 -131079 740891 581865 -191711 -383018 273044 476880\n3 1\n4 1\n6 9\n3 8\n1 6\n10 5\n5 6\n1 5\n4 3\n7 1\n7 4\n10 3"},{"iden":"sample output 2","content":"2306209"},{"iden":"sample input 3","content":"4 2\n1 1 1 1\n1 1 -1 -1\n1 2\n3 4"},{"iden":"sample output 3","content":"4\n\nThe given graph is not necessarily connected."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}