Sum of Abs

AtCoder

IDarc107_f

Time2000ms

Memory256MB

Difficulty—

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$. Snuke 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: * The score is the sum of the scores of all connected components. * The score of a connected component is the absolute value of the sum of $B_i$ of the vertices in the connected component. Snuke's _profit_ is $($score$)$ $-$ $($the sum of costs$)$. Find the maximum possible profit Snuke can gain. ## Constraints * $1 \leq N \leq 300$ * $1 \leq M \leq 300$ * $1 \leq A_i \leq 10^6$ * $-10^6 \leq B_i \leq 10^6$ * $1 \leq U_i,V_i \leq N$ * The given graph does not contain self loops or multiple edges. * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $M$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_N$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$ [samples]

Samples

Input #1

Output #1

1

Deleting 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$.

Input #2

10 12
733454 729489 956011 464983 822120 364691 271012 762026 751760 965431
-817837 -880667 -822819 -131079 740891 581865 -191711 -383018 273044 476880
3 1
4 1
6 9
3 8
1 6
10 5
5 6
1 5
4 3
7 1
7 4
10 3

Output #2

Input #3

Output #3

4

The given graph is not necessarily connected.

API Response (JSON)

{
  "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 inte...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments