Down Below

题意翻译

给定一张无向图 $G$，除了 $1$ 节点每个节点有两个权值 $a_i,b_i$。 你初始在 $1$ 节点，有一个权值 $val$，你可以从 $u$ 移动到 $v$ 当且仅当： - $u,v\in G$ - 你当前的 $val>a_v$ - 如果这不是第一次移动，移动到 $u$ 前的一个节点不能是 $v$ 移动了之后，$val\leftarrow val+b_v$。 你可以重复经过一个点，但是你无法重复获得 $b$ 的加成。 你需要经过所有的点，问你初始 $val$ 至少是多少。 数据范围 $n\le 10^3,m\le 2\times 10^3$，保证图联通。 任何点的度数都 $\ge 2$。

题目描述

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.

输入输出格式

输入格式

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

输出格式

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.

输入输出样例

输入样例 #1

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

输出样例 #1

15
15
19

说明

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