问题描述

有一个简单的无向图，有 $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$ 日元。
• 向你所站的顶点 $v$ 捐赠 $B_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 日元。
• 向顶点 4 捐赠 2 日元。现在你有 4 日元。
• 移动到顶点 3。这是可能的，因为你至少有 4 日元。
• 向顶点 3 捐赠 1 日元。现在你有 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