Down Below
Contest: Codeforces Round 740 (Div. 1, based on VK Cup 2021 - Final (Engine))
Difficulty rating: 3000
Tags: binary search, dfs and similar, graphs, greedy, meet-in-the-middle, shortest paths

In a certain video game, the player controls a hero characterized by a single integer value: power.

On the current level, the hero got into a system of $$$n$$$ caves numbered from $$$1$$$ to $$$n$$$, and $$$m$$$ tunnels between them. Each tunnel connects two distinct caves. Any two caves are connected with at most one tunnel. Any cave can be reached from any other cave by moving via tunnels.

The hero starts the level in cave $$$1$$$, and every other cave contains a monster.

The hero can move between caves via tunnels. If the hero leaves a cave and enters a tunnel, he must finish his movement and arrive at the opposite end of the tunnel.

The hero can use each tunnel to move in both directions. However, the hero can not use the same tunnel twice in a row. Formally, if the hero has just moved from cave $$$i$$$ to cave $$$j$$$ via a tunnel, he can not head back to cave $$$i$$$ immediately after, but he can head to any other cave connected to cave $$$j$$$ with a tunnel.

It is known that at least two tunnels come out of every cave, thus, the hero will never find himself in a dead end even considering the above requirement.

To pass the level, the hero must beat the monsters in all the caves. When the hero enters a cave for the first time, he will have to fight the monster in it. The hero can beat the monster in cave $$$i$$$ if and only if the hero's power is strictly greater than $$$a_i$$$. In case of beating the monster, the hero's power increases by $$$b_i$$$. If the hero can't beat the monster he's fighting, the game ends and the player loses.

After the hero beats the monster in cave $$$i$$$, all subsequent visits to cave $$$i$$$ won't have any consequences: the cave won't have any monsters, and the hero's power won't change either.

Find the smallest possible power the hero must start the level with to be able to beat all the monsters and pass the level.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 1000$$$; $$$n \le m \le min(\frac{n(n-1)}{2}, 2000)$$$) — the number of caves and tunnels.

The second line contains $$$n-1$$$ integers $$$a_2, a_3, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — values the hero's power are compared to while fighting monsters in caves $$$2, 3, \ldots, n$$$.

The third line contains $$$n-1$$$ integers $$$b_2, b_3, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — increases applied to the hero's power for beating monsters in caves $$$2, 3, \ldots, n$$$.

Each of the next $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$) — the numbers of caves connected with a tunnel.

No two caves are connected with more than one tunnel. Any cave can be reached from any other cave by moving via tunnels. At least two tunnels come out of every cave.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$2000$$$.

Output format:
For each test case print a single integer — the smallest possible power the hero must start the level with to be able to beat all the monsters and pass the level.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
In the first test case, the hero can pass the level with initial power $$$15$$$ as follows:

- move from cave $$$1$$$ to cave $$$2$$$: since $$$15 > 11$$$, the hero beats the monster, and his power increases to $$$15 + 8 = 23$$$;
- move from cave $$$2$$$ to cave $$$3$$$: since $$$23 > 22$$$, the hero beats the monster, and his power increases to $$$23 + 7 = 30$$$;
- move from cave $$$3$$$ to cave $$$4$$$: since $$$30 > 13$$$, the hero beats the monster, and his power increases to $$$30 + 5 = 35$$$.

In the second test case, the situation is similar except that the power increases for beating monsters in caves $$$2$$$ and $$$4$$$ are exchanged. The hero can follow a different route, $$$1 \rightarrow 4 \rightarrow 3 \rightarrow 2$$$, and pass the level with initial power $$$15$$$.

In the third test case, the hero can pass the level with initial power $$$19$$$ as follows:

- move from cave $$$1$$$ to cave $$$2$$$: since $$$19 > 10$$$, the hero beats the monster, and his power increases to $$$19 + 7 = 26$$$;
- move from cave $$$2$$$ to cave $$$4$$$: since $$$26 > 20$$$, the hero beats the monster, and his power increases to $$$26 + 10 = 36$$$;
- move from cave $$$4$$$ to cave $$$5$$$: since $$$36 > 30$$$, the hero beats the monster, and his power increases to $$$36 + 5 = 41$$$;
- move from cave $$$5$$$ to cave $$$2$$$: there is no monster in this cave anymore, nothing happens;
- move from cave $$$2$$$ to cave $$$3$$$: since $$$41 > 40$$$, the hero beats the monster, and his power increases to $$$41 + 2 = 43$$$.

Example input:
3
4 4
11 22 13
8 7 5
1 2
2 3
3 4
4 1
4 4
11 22 13
5 7 8
1 2
2 3
3 4
4 1
5 7
10 40 20 30
7 2 10 5
1 2
1 5
2 3
2 4
2 5
3 4
4 5

Example output:
15
15
19

Editorial:
Let's find the smallest possible initial power with binary search. Suppose the initial power is $$$p$$$.
The main idea behind the solution is to maintain a set of caves where we have beaten all the monsters, and try to extend the set by finding "augmenting" paths.
However, we can not just go in an arbitrary unvisited cave and pretend we add it to the set: since we are not allowed to turn back, it might happen that we can not move forward anymore because we don't have enough power. It's important that we must be able to reach any cave inside the set only going through caves belonging to the set itself.
Initially, the set contains just cave $$$1$$$.
What can an augmenting path look like?
• The path can start somewhere inside the set, go out of the set, follow a simple route visiting some new caves (and beating monsters inside them), and go back to a cave belonging to the set. For example, if caves $$$1$$$ and $$$2$$$ belong to the set, the route can look like $$$1 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 2$$$, and we can add caves $$$3$$$, $$$4$$$, and $$$5$$$ to the set.
• Alternatively, instead of going back to a cave from the set, the path might go into a cave belonging to the route. For example, if caves $$$1$$$ and $$$2$$$ belong to the set, the route can look like $$$1 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 4$$$, and we can add caves $$$3$$$, $$$4$$$, $$$5$$$, and $$$6$$$ to the set.
How do we find any augmenting path satisfying us?
It turns out that we can use the following property. Suppose we have a path $$$v \rightarrow u_1 \rightarrow u_2 \rightarrow \ldots \rightarrow u_k \rightarrow x$$$ (where $$$v$$$ is the only cave belonging to the set) that we can follow and beat all the monsters in the caves we visit. Suppose that we have another such path $$$v' \rightarrow u'_1 \rightarrow u'_2 \rightarrow \ldots \rightarrow u'_{k'} \rightarrow x$$$. Suppose that following the former path, we arrive at $$$x$$$ with the same or higher power than following the latter path. In this case, notice that
Thus, we can simply use BFS or DFS to find all reachable caves. Once we find a path leading back into the set, or we find two different paths leading into the same unvisited cave, we can build an augmenting path, extend the set, and start over, until the set contains all caves (in which case we can try to decrease the initial power level $$$p$$$) or until we can not find any augmenting path (in which case we must increase $$$p$$$).
At each binary search iteration, we can have at most $$$n$$$ augmenting paths and we find each of them in $$$O(m)$$$. Thus, the time complexity of the solution is $$$O(nm \log{a_{max}})$$$.