CF1558E.Down Below

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.

在某个视频游戏中，玩家操控一名英雄，该英雄由一个整数属性——力量值（power）表征。

在当前关卡中，英雄进入了一个由 $n$ 个洞穴（编号从 $1$ 到 $n$）和 $m$ 条连接它们的隧道构成的系统。每条隧道连接两个不同的洞穴；任意两个洞穴之间至多只有一条隧道；且任意洞穴均可通过若干隧道到达其他任意洞穴（即图是连通的）。

英雄从洞穴 $1$ 开始本关；其余每个洞穴中均有一只怪物。

英雄可通过隧道在洞穴间移动。若英雄离开一个洞穴并进入一条隧道，则他必须完成此次移动，抵达该隧道的另一端。

每条隧道均可双向通行。但英雄不能连续两次使用同一条隧道。形式化地说：若英雄刚通过某条隧道从洞穴 $i$ 移动至洞穴 $j$，则他接下来不能立即沿同一条隧道返回洞穴 $i$；但他可以前往任意其他与洞穴 $j$ 相连的洞穴（即除 $i$ 外所有与 $j$ 邻接的洞穴）。

已知每个洞穴至少连出两条隧道，因此即使考虑上述“不可折返”的限制，英雄也永远不会陷入死路。

为通过本关，英雄必须击败所有洞穴中的怪物。当英雄首次进入某个洞穴时，他必须与其中的怪物战斗。英雄仅当其当前力量值严格大于 $a_i$ 时，才能击败洞穴 $i$ 中的怪物；若成功击败，则英雄的力量值增加 $b_i$。若英雄无法击败当前所面对的怪物，则游戏结束，玩家失败。

英雄击败洞穴 $i$ 中的怪物后，此后每次再进入洞穴 $i$ 均不会产生任何影响：该洞穴不再有怪物，英雄的力量值也不会再发生变化。

请找出英雄为能击败所有怪物并通关本关，所需拥有的最小初始力量值。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$3 \le n \le 1000$；$n \le m \le \min\left(\frac{n(n-1)}{2}, 2000\right)$），分别表示洞穴数量和隧道数量。

每个测试用例的第二行包含 $n-1$ 个整数 $a_2, a_3, \ldots, a_n$（$1 \le a_i \le 10^9$）——英雄在洞穴 $2, 3, \ldots, n$ 中与怪物战斗时，其力量值需比较的阈值。

每个测试用例的第三行包含 $n-1$ 个整数 $b_2, b_3, \ldots, b_n$（$1 \le b_i \le 10^9$）——英雄击败洞穴 $2, 3, \ldots, n$ 中的怪物后，其力量值所获得的提升量。

接下来的 $m$ 行中，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$；$u_i \ne v_i$）——表示由一条隧道相连的两个洞穴的编号。

任意两个洞穴之间至多只有一条隧道相连。任意洞穴均可通过隧道到达其他任意洞穴。每个洞穴至少连接两条隧道。

保证所有测试用例的 $n$ 之和不超过 $1000$，且所有测试用例的 $m$ 之和不超过 $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.

对于每个测试用例，输出一个整数——英雄开始该关卡时所需的最小初始能力值，以确保能够击败所有怪物并通关。

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 \gt 11$, the hero beats the monster, and his power increases to $15 + 8 = 23$;
• move from cave $2$ to cave $3$: since $23 \gt 22$, the hero beats the monster, and his power increases to $23 + 7 = 30$;
• move from cave $3$ to cave $4$: since $30 \gt 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 \gt 10$, the hero beats the monster, and his power increases to $19 + 7 = 26$;
• move from cave $2$ to cave $4$: since $26 \gt 20$, the hero beats the monster, and his power increases to $26 + 10 = 36$;
• move from cave $4$ to cave $5$: since $36 \gt 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 \gt 40$, the hero beats the monster, and his power increases to $41 + 2 = 43$.

在第一个测试用例中，英雄可以以初始力量值 $15$ 通关关卡，过程如下：

• 从洞穴 $1$ 移动到洞穴 $2$：由于 $15 \gt 11$，英雄击败怪物，其力量值增加至 $15 + 8 = 23$；
• 从洞穴 $2$ 移动到洞穴 $3$：由于 $23 \gt 22$，英雄击败怪物，其力量值增加至 $23 + 7 = 30$；
• 从洞穴 $3$ 移动到洞穴 $4$：由于 $30 \gt 13$，英雄击败怪物，其力量值增加至 $30 + 5 = 35$。

在第二个测试用例中，情形类似，只是洞穴 $2$ 和洞穴 $4$ 中击败怪物所获得的力量值增益被互换了。英雄可选择另一条路径 $1 \rightarrow 4 \rightarrow 3 \rightarrow 2$，并以初始力量值 $15$ 通关关卡。

在第三个测试用例中，英雄可以以初始力量值 $19$ 通关关卡，过程如下：

• 从洞穴 $1$ 移动到洞穴 $2$：由于 $19 \gt 10$，英雄击败怪物，其力量值增加至 $19 + 7 = 26$；
• 从洞穴 $2$ 移动到洞穴 $4$：由于 $26 \gt 20$，英雄击败怪物，其力量值增加至 $26 + 10 = 36$；
• 从洞穴 $4$ 移动到洞穴 $5$：由于 $36 \gt 30$，英雄击败怪物，其力量值增加至 $36 + 5 = 41$；
• 从洞穴 $5$ 移动到洞穴 $2$：该洞穴中已无怪物，不发生任何事件；
• 从洞穴 $2$ 移动到洞穴 $3$：由于 $41 \gt 40$，英雄击败怪物，其力量值增加至 $41 + 2 = 43$。