分数: 1000 点
问题陈述
有一个简单的无向图 N 顶点和 M 边缘。 顶点已编号 1 通过 N,并且边缘已编号 1 通过 M。 边缘 i 连接顶点 U_i 和 V_i。 另外,顶点 i 有两个预定整数 A_i 和 B_i。 您将在此图表上玩以下游戏。
首先,选择一个顶点并站在它上面, W 日元(日本货币)在你的口袋里。 在这里, A_s \leq W 必须持有,其中 s 是您选择的顶点。 然后,以任意顺序执行任意次数的以下两种操作:
- 选择一个顶点 v 通过一条边直接连接到您所站立的顶点,并移动到顶点 v。在这里,你至少需要有 当你执行此动作时, A_v 日元在你的口袋里。
- 捐赠 B_v 日元到顶点 v 你站在上面。在这里,你口袋里的钱不能少于 0 日元。
当您向每个顶点捐赠一次时,您就赢得了游戏。 找出最小的初始金额 W 使您能够赢得比赛。
约束
- 1 \leq N \leq 10^5
- N-1 \leq M \leq 10^5
- 1 \leq A_i,B_i \leq 10^9
- 1 \leq U_i < V_i \leq N
- 给定的图是连通的且简单的(任意一对顶点之间至多有一条边)。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 A_2 B_2 : A_N B_N U_1 V_1 U_2 V_2 : U_M V_M
输出
打印最小初始金额 W 使您能够赢得比赛。
示例输入 1
4 5 3 1 1 2 4 1 6 2 1 2 2 3 2 4 1 4 3 4
示例输出 1
6
如果您有 6 日元初始,您可以通过以下方式赢得游戏:
- 站在顶点 4。这是可能的,因为您的数量不少于 6 日元。
- 捐赠 2 日元 至 顶点 4。现在你有 4 日元。
- 移动到顶点 3。这是可能的,因为您的数量不少于 4 日元。
- 捐赠 1 日元 至 顶点 3。现在你有 3 日元。
- 移动到顶点 2。这是可能的,因为您的数量不少于 1 日元。
- 移动到顶点 1。这是可能的,因为您的数量不少于 3 日元。
- 捐赠 1 日元 至 顶点 1。现在你有 2 日元。
- 移动到顶点 2。这是可能的,因为您的数量不少于 1 日元。
- 捐赠 2 日元 至 顶点 2。现在你有 0 日元。
如果您的数量少于 6 日元一开始,你无法赢得比赛。因此,答案是 6.
示例输入 2
5 8 6 4 15 13 15 19 15 1 20 7 1 3 1 4 1 5 2 3 2 4 2 5 3 5 4 5
示例输出 2
44
示例输入 3
9 10 131 2 98 79 242 32 231 38 382 82 224 22 140 88 209 70 164 64 6 8 1 6 1 4 1 3 4 7 4 9 3 7 3 9 5 9 2 5
示例输出 3
582