← 返回题目列表

Codeforces · 1558/E

E. 下面

中文机器翻译题面 查看原题

在某个视频游戏中,玩家控制一个由单个整数值表征的英雄:力量。

在当前关卡中,英雄进入了一个由$$$n$$$洞穴组成的系统,编号从$$$1$$$到$$$n$$$,以及它们之间的$$$m$$$隧道。每条隧道连接两个不同的洞穴。任意两个洞穴最多有一条隧道相连。任何洞穴都可以通过隧道从任何其他洞穴到达。

英雄在洞穴 $$$1$$$ 中开始关卡,并且每个其他洞穴都包含一个怪物。

英雄可以通过隧道在洞穴之间移动。如果英雄离开洞穴并进入隧道,他必须完成移动并到达隧道的另一端。

英雄可以使用每个隧道双向移动。然而,英雄不能连续两次使用同一个隧道。正式来说,如果英雄刚刚通过隧道从洞穴$$$i$$$移动到洞穴$$$j$$$,他不能立即返回洞穴$$$i$$$,但他可以前往通过隧道连接到洞穴$$$j$$$的任何其他洞穴。

众所周知,每个洞穴至少有两条隧道,因此,即使考虑到上述要求,英雄也永远不会发现自己陷入死胡同。

要通过关卡,英雄必须击败所有洞穴中的怪物。当英雄第一次进入洞穴时,他必须与里面的怪物战斗。当且仅当英雄的力量严格大于$$$a_i$$$时,英雄才能击败洞穴中的怪物$$$i$$$。如果击败怪物,英雄的力量会增加$$$b_i$$$。如果英雄无法击败他正在战斗的怪物,游戏就会结束,玩家就输了。

英雄击败$$$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$$$。

输出

对于每个测试用例,打印一个整数 - 英雄在开始关卡时必须具有的最小可能力量,以便能够击败所有怪物并通过关卡。

示例

输入 #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

注意

在第一个测试用例中,英雄可以通过初始力量 $$$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$$$。