CF1558E Down Below

在某款视频游戏中，玩家控制的英雄由一个整数值“力量”来描述。 在当前关卡中，英雄进入了一个由 $n$ 个洞穴组成的系统，这些洞穴编号为 $1$ 到 $n$，并且有 $m$ 条隧道连接这些洞穴。每条隧道连接两个不同的洞穴。任意两洞穴之间最多只有一条隧道。通过隧道可以从任意一个洞穴到达另一个洞穴。 英雄从洞穴 $1$ 开始，每个其他洞穴中都有一只怪物。 英雄可以通过隧道在洞穴之间移动。如果英雄离开一个洞穴并进入一条隧道，他必须完成移动并到达隧道的另一端。 每条隧道都可以双向通行。然而，英雄不能连续两次使用同一条隧道。具体来说，如果英雄刚刚通过一条隧道从洞穴 $i$ 移动到洞穴 $j$，那么他不能立刻通过同一条隧道返回洞穴 $i$，但他可以通过与洞穴 $j$ 相连的其他隧道前往其他洞穴。 已知每个洞穴至少有两条隧道相连，因此即使考虑上述限制，英雄也不会陷入死胡同。 要通过本关，英雄必须击败所有洞穴中的怪物。当英雄第一次进入洞穴 $i$ 时，必须与其中的怪物战斗。只有当英雄的力量严格大于 $a_i$ 时，才能击败洞穴 $i$ 的怪物。击败怪物后，英雄的力量会增加 $b_i$。如果英雄无法击败当前的怪物，游戏结束，玩家失败。 英雄击败洞穴 $i$ 的怪物后，之后再进入该洞穴不会有任何影响：该洞穴中已无怪物，英雄的力量也不会再发生变化。 请你求出英雄能够通过本关所需的最小初始力量。

每个测试用例包含多组数据。第一行包含测试用例个数 $t$（$1 \le t \le 100$）。每组测试用例的描述如下。 每组测试用例的第一行包含两个整数 $n$ 和 $m$（$3 \le n \le 1000$；$n \le m \le \min(\frac{n(n-1)}{2}, 2000)$），分别表示洞穴数和隧道数。 第二行包含 $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$。

对于每组测试用例，输出一个整数，表示英雄能够通过本关所需的最小初始力量。

在第一个测试用例中，英雄可以以初始力量 $15$ 通过本关，过程如下： - 从洞穴 $1$ 移动到洞穴 $2$：由于 $15 > 11$，英雄击败怪物，力量变为 $15 + 8 = 23$； - 从洞穴 $2$ 移动到洞穴 $3$：由于 $23 > 22$，英雄击败怪物，力量变为 $23 + 7 = 30$； - 从洞穴 $3$ 移动到洞穴 $4$：由于 $30 > 13$，英雄击败怪物，力量变为 $30 + 5 = 35$。 在第二个测试用例中，情况类似，只是击败洞穴 $2$ 和 $4$ 的怪物后力量增加值交换了。英雄可以选择不同的路线 $1 \rightarrow 4 \rightarrow 3 \rightarrow 2$，同样以初始力量 $15$ 通过本关。 在第三个测试用例中，英雄可以以初始力量 $19$ 通过本关，过程如下： - 从洞穴 $1$ 移动到洞穴 $2$：由于 $19 > 10$，英雄击败怪物，力量变为 $19 + 7 = 26$； - 从洞穴 $2$ 移动到洞穴 $4$：由于 $26 > 20$，英雄击败怪物，力量变为 $26 + 10 = 36$； - 从洞穴 $4$ 移动到洞穴 $5$：由于 $36 > 30$，英雄击败怪物，力量变为 $36 + 5 = 41$； - 从洞穴 $5$ 移动回洞穴 $2$：此时该洞穴已无怪物，无事发生； - 从洞穴 $2$ 移动到洞穴 $3$：由于 $41 > 40$，英雄击败怪物，力量变为 $41 + 2 = 43$。 由 ChatGPT 4.1 翻译