← 返回题目列表

AtCoder · arc098_d

F. 捐赠

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

分数: 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