Down Below

Description:

Input:

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:

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.

Sample 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

Sample Output:

15
15
19

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