{"problem":{"name":"Sum of Abs","description":{"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 inte","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc107_f"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc107_f","tags":[],"sample_group":[["4 4\n4 1 2 3\n0 2 -3 1\n1 2\n2 3\n3 4\n4 2","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$."],["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","2306209"],["4 2\n1 1 1 1\n1 1 -1 -1\n1 2\n3 4","4\n\nThe given graph is not necessarily connected."]],"created_at":"2026-03-03 11:01:13"}}