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

-----Output-----
Print the maximum possible profit Snuke can gain.

-----Sample Input-----
4 4
4 1 2 3
0 2 -3 1
1 2
2 3
3 4
4 2

-----Sample Output-----
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.

Difficulty: competition

Starter code:

Solutions:
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

# node : 0<=i<=3*N-1, i:minus i+1: delete i+2: plus
# start : 3*N
# goal : 3*N+1

EDGE=[dict() for i in range(3*N+2)]
V=3*N+2
start=3*N
goal=3*N+1

for i in range(N):
    EDGE[start][3*i] = -B[i] + (1<<30)
    EDGE[3*i][3*i+1] = A[i] + (1<<30)
    EDGE[3*i+1][3*i+2] = B[i] + (1<<30)
    EDGE[3*i+2][goal] = float("inf")

for i in range(M):
    x,y=map(int,input().split())
    x-=1
    y-=1

    EDGE[3*x+1][3*y] = float("inf")
    EDGE[3*y+1][3*x] = float("inf")

ANS=0
while True:
    USED=[0]*V
    ROUTE=[-1]*V
    Q=[(start,float("inf"))]
    
    while Q: # DFS
        NOW,cost=Q.pop()
        if NOW==goal:
            break

        for to in EDGE[NOW]:
            if USED[to]==0 and EDGE[NOW][to]!=0: 
                ROUTE[to]=NOW
                USED[to]=1
                Q.append((to,min(cost,EDGE[NOW][to])))
    else:
        break
    
    ANS+=cost
    i=goal
    while i!=start: # goalからたどり,Routeを使ってEDGEの更新
        j=ROUTE[i]
        EDGE[j][i]-=cost # 使ったルートをいけなく更新
        if j in EDGE[i]:
            EDGE[i][j]+=cost # 逆向きに進めるようにする.これらを重みつきにすれ普通のフロー
        else:
            EDGE[i][j]=cost
            
        i=j
        
print(-(ANS-(N<<30)))

# Dinic's algorithm
from collections import deque
class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
edge = [tuple(map(int,input().split())) for i in range(M)]

G = Dinic(2*N+2)
res = 0
for i in range(1,N+1):
    if B[i-1]>0:
        res += B[i-1]
        G.add_edge(0,i,B[i-1])
        G.add_edge(0,N+i,B[i-1])
        G.add_edge(N+i,i,A[i-1])
    else:
        G.add_edge(i,2*N+1,-B[i-1])
        res += -B[i-1]
        G.add_edge(N+i,2*N+1,-B[i-1])
        G.add_edge(N+i,i,A[i-1])
    G.add_edge(i,N+i,10**15)

for u,v in edge:
    G.add_edge(u,N+v,10**15)
    G.add_edge(v,N+u,10**15)

res -= G.flow(0,2*N+1)

print(res)

INF = float("inf")
INF = 2<<30

class Dinic:
    def __init__(self, n):
        self.lvl = [0] * n
        self.ptr = [0] * n
        self.q = [0] * n
        self.adj = [[] for _ in range(n)]

    def add_edge(self, a, b, c, rcap=0):
        self.adj[a].append([b, len(self.adj[b]), c, 0])
        self.adj[b].append([a, len(self.adj[a]) - 1, rcap, 0])

    def dfs(self, v, t, f):
        if v == t or not f:
            return f

        for i in range(self.ptr[v], len(self.adj[v])):
            e = self.adj[v][i]
            if self.lvl[e[0]] == self.lvl[v] + 1:
                p = self.dfs(e[0], t, min(f, e[2] - e[3]))
                if p:
                    self.adj[v][i][3] += p
                    self.adj[e[0]][e[1]][3] -= p
                    return p
            self.ptr[v] += 1

        return 0

    def calc(self, s, t):
        flow, self.q[0] = 0, s
        for l in range(31):  # l = 30 maybe faster for random data
            while True:
                self.lvl, self.ptr = [0] * len(self.q), [0] * len(self.q)
                qi, qe, self.lvl[s] = 0, 1, 1
                while qi < qe and not self.lvl[t]:
                    v = self.q[qi]
                    qi += 1
                    for e in self.adj[v]:
                        if not self.lvl[e[0]] and (e[2] - e[3]) >> (30 - l):
                            self.q[qe] = e[0]
                            qe += 1
                            self.lvl[e[0]] = self.lvl[v] + 1

                p = self.dfs(s, t, INF)
                while p:
                    flow += p
                    p = self.dfs(s, t, INF)

                if not self.lvl[t]:
                    break

        return flow

n, m = list(map(int, input().split()))
s = 2 * n
t = 2 * n + 1
MF = Dinic(2 * n + 2)
out = 0
A = list(map(int, input().split()))
B = list(map(int, input().split()))
for i in range(n):
    a = A[i]
    v = B[i]
    out += a
    MF.add_edge(i, i + n, INF)
    if a - v > 0:
        MF.add_edge(s, i, a - v)
    else:
        out += v - a
    if a + v > 0:
        MF.add_edge(i + n, t, a + v)
    else:
        out -= v + a
for i in range(m):
    u, v = list(map(int, input().split()))
    MF.add_edge(u - 1, v - 1 + n, INF)
    MF.add_edge(v - 1, u - 1 + n, INF)
print((out - MF.calc(s,t)))
    



"""

https://atcoder.jp/contests/arc107/tasks/arc107_f

絶対値なので、頂点を正側・府側に割り当てて、その間に辺があってはいけない
とする
頂点が消える場合もある…

全部正の寄与として答えにあらかじめ足しておく
元が+の場合、 -側にあると -2A の被害・消されると-Aの被害
元が-の場合、 +側にあると -2A の被害・消されると-Aの被害

基本的に別側にあると被害のみ記述できる
頂点を2倍する…しか考えられない

(+基準点)
||
aA
と2つ繋げると、両方反対側で-2A・片方だけ反対で-A・両方基準点側で-0を表現できる

bB
||
(-基準点)

start 
|| ||  ←+側
------
|| ||
aA bB  ←-側
|| ||
|| ||
 GOAL


aA/
a/A
/aA
の3通りに絞る
Aが+側になる & bが負側はまずい
→inf

"""

import sys
from sys import stdin

from collections import defaultdict
from collections import deque
import sys
sys.setrecursionlimit(200000)

def Dinic_DFS(v,g,maxflow,lines,cost,level):
    if v == g:
        return maxflow

    realflow = 0
    tmp = [i for i in lines[v]]
    for nex in tmp:
        if level[nex] > level[v]:
            
            plusflow = Dinic_DFS(nex,g,min(maxflow , cost[v][nex]),lines,cost,level)
            cost[v][nex] -= plusflow
            if cost[v][nex] == 0:
                lines[v].remove(nex)
            if cost[nex][v] == 0:
                lines[nex].add(v)
            cost[nex][v] += plusflow
            
            realflow += plusflow
            maxflow -= plusflow

            if maxflow <= 0:
                return realflow

    return realflow

def Dinic(s,g,lines,cost):

    N = len(cost)
    ans = 0

    while True:

        #bfs
        q = deque([s])
        level = [float("inf")] * N
        level[s] = 0
        while q:
            now = q.popleft()
            for nex in lines[now]:

                if level[nex] > level[now] + 1:
                    level[nex] = level[now] + 1
                    q.append(nex)

        if level[g] == float("inf"):
            return ans

        #dfs
        delta_flow = Dinic_DFS(s,g,float("inf"),lines,cost,level)
        while delta_flow > 0:
            ans += delta_flow
            delta_flow = Dinic_DFS(s,g,float("inf"),lines,cost,level)

inf = 10**18
N,M = map(int,stdin.readline().split())
A = list(map(int,stdin.readline().split()))
B = list(map(int,stdin.readline().split()))

s  = 2*N
g  = 2*N+1

ans = 0
for i in range(N):
    ans += abs(B[i])

lines = defaultdict(set)
cost = [ [0] * (2*N+2) for i in range(2*N+2) ]

for i in range(N):

    lines[i+N].add(i)
    cost[i+N][i] += inf

    if B[i] >= 0:
        
        lines[s].add(i)
        cost[s][i] += 2*B[i]

        lines[i].add(N+i)
        cost[i][N+i] += A[i]+B[i]
    
    elif B[i] < 0:

        lines[i].add(N+i)
        cost[i][N+i] += A[i]+abs(B[i])

        lines[i+N].add(g)
        cost[i+N][g] += 2*abs(B[i])

for i in range(M):
    u,v = map(int,stdin.readline().split())
    u -= 1
    v -= 1

    lines[u+N].add(v)
    cost[u+N][v] += inf

    lines[v+N].add(u)
    cost[v+N][u] += inf

print (ans - Dinic(s,g,lines,cost))

import sys
input = sys.stdin.readline

N,M=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

# node : 0<=i<=3*N-1, i:minus i+1: delete i+2: plus
# start : 3*N
# goal : 3*N+1

EDGE=[dict() for i in range(3*N+2)]
V=3*N+2
start=3*N
goal=3*N+1

for i in range(N):
    EDGE[start][3*i] = -B[i] + (1<<30)
    EDGE[3*i][3*i+1] = A[i] + (1<<30)
    EDGE[3*i+1][3*i+2] = B[i] + (1<<30)
    EDGE[3*i+2][goal] = float("inf")

for i in range(M):
    x,y=map(int,input().split())
    x-=1
    y-=1

    EDGE[3*x+1][3*y] = float("inf")
    EDGE[3*y+1][3*x] = float("inf")

ANS=0
while True:
    USED=[0]*V
    ROUTE=[-1]*V
    Q=[(start,float("inf"))]
    
    while Q: # DFS
        NOW,cost=Q.pop()
        if NOW==goal:
            break

        for to in EDGE[NOW]:
            if USED[to]==0 and EDGE[NOW][to]!=0: 
                ROUTE[to]=NOW
                USED[to]=1
                Q.append((to,min(cost,EDGE[NOW][to])))
    else:
        break
    
    ANS+=cost
    i=goal
    while i!=start: # goalからたどり,Routeを使ってEDGEの更新
        j=ROUTE[i]
        EDGE[j][i]-=cost # 使ったルートをいけなく更新
        if j in EDGE[i]:
            EDGE[i][j]+=cost # 逆向きに進めるようにする.これらを重みつきにすれ普通のフロー
        else:
            EDGE[i][j]=cost
            
        i=j
        
print(-(ANS-(N<<30)))

import sys
readline = sys.stdin.readline
import collections
class Dinic:
    def __init__(self, vnum):
        self.edge = [[] for i in range(vnum)]
        self.n = vnum
        # infはint型の方が良いかもね
        self.inf = 10**9+7
    def addedge(self, st, en, c):
        self.edge[st].append([en, c, len(self.edge[en])])
        self.edge[en].append([st, 0, len(self.edge[st])-1])
    def bfs(self, vst):
        dist = [-1]*self.n
        dist[vst] = 0
        Q = collections.deque([vst])
        while Q:
            nv = Q.popleft()
            for vt, c, r in self.edge[nv]:
                if dist[vt] == -1 and c > 0:
                    dist[vt] = dist[nv] + 1
                    Q.append(vt)
        self.dist = dist
    def dfs(self, nv, en, nf):
        nextv = self.nextv
        if nv == en:
            return nf
        dist = self.dist
        ist = nextv[nv]
        for i, (vt, c, r) in enumerate(self.edge[nv][ist:], ist):
            if dist[nv] < dist[vt] and c > 0:
                df = self.dfs(vt, en, min(nf, c))
                if df > 0:
                    self.edge[nv][i][1] -= df
                    self.edge[vt][r][1] += df
                    return df
            nextv[nv] += 1
        return 0
    def getmf(self, st, en):
        mf = 0
        while True:
            self.bfs(st)
            if self.dist[en] == -1:
                break
            self.nextv = [0]*self.n
            while True:
                fl = self.dfs(st, en, self.inf)
                if fl > 0:
                    mf += fl
                else:
                    break
        return mf


N, M = list(map(int, readline().split()))
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))


INF = 10**9+7
D = Dinic(2*N+2)
st = 2*N
en = st+1

ans = 0
for i in range(N):
    b = abs(B[i])
    if B[i] < 0:
        D.addedge(st, 2*i, 2*b)
    else:
        D.addedge(2*i+1, en, 2*b)
    D.addedge(2*i, 2*i+1, A[i] + b)
    ans += b

for _ in range(M):
    u, v = list(map(int, readline().split()))
    u -= 1
    v -= 1
    D.addedge(2*u+1, 2*v, INF)
    D.addedge(2*v+1, 2*u, INF)

print((ans - D.getmf(st, en)))