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: VERY_HARD

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()))
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:
		(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:
		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)))


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):
			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))


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:
		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
		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
readline = sys.stdin.readline
import collections

class Dinic:

	def __init__(self, vnum):
		self.edge = [[] for i in range(vnum)]
		self.n = vnum
		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))