题目描述

有 $n$ 只史莱姆，编号从 $1 \sim n$。这些史莱姆之间有 $m$ 对朋友关系，第 $i$ 对朋友关系用 $u_i, v_i$ 描述，表示编号为 $u_i$ 和 $v_i$ 的史莱姆互相是好朋友。（朋友关系不能传递，即朋友的朋友不是朋友，只有直接相连的是朋友）。

每只史莱姆都有一个体重属性，第 $i$ 只史莱姆的体重为 $a_i$。

每只史莱姆都有些麻烦需要解决，第 $i$ 只史莱姆的需要解决的麻烦数量为 $b_i$。

作为冒险者，你可以帮助史莱姆解决麻烦来获得经验值。你可以完成若干次操作，每次操作包含下面两个步骤：

1. 选择一只麻烦数不为 $0$ 的史莱姆，让他的麻烦数减少 $1$。
2. 可以挑选第一步中选择的史莱姆的一个或多个朋友，但必须满足这些朋友的体重之和严格小于这个史莱姆的体重，然后可以让这些朋友的麻烦数增加 $1$。如果无法找到满足条件的朋友们，可以不做这一步。

你需要尽可能多地进行操作，求最多能进行多少次操作（题目保证能在有限次操作后结束）。

输入格式

第一行为空格隔开的两个整数：$n, m$。

第二行为空格隔开的 $n$ 个整数：$a_1 \sim a_n$。

第三行为空格隔开的 $n$ 个整数：$b_1 \sim b_n$。

接下来 $m$ 行，每行为空格隔开的两个整数，第 $i$ 行为 $u_i, v_i$。

输出格式

输出一个整数，即最多的操作次数。

样例

6 6
4 4 1 3 2 9
1 0 0 0 0 1
6 5
5 4
4 6
3 4
6 2
1 2

5

样例解释

• 初始六只史莱姆的麻烦数分别为 $(1, 0, 0, 0, 0, 1)$。
• 解决 $6$ 号史莱姆的麻烦，然后给他的朋友 $5, 4$ 号的麻烦数加 $1$，麻烦数变为了 $(1, 0, 0, 1, 1, 0)$。
• 解决 $5$ 号史莱姆的麻烦，麻烦数变为了 $(1, 0, 0, 1, 0, 0)$。
• 解决 $1$ 号史莱姆的麻烦，麻烦数变为了 $(0, 0, 0, 1, 0, 0)$。
• 解决 $4$ 号史莱姆的麻烦，然后给他的朋友 $5$ 号的麻烦数加 $1$，麻烦数变为了 $(0, 0, 0, 0, 1, 0)$。
• 解决 $5$ 号史莱姆的麻烦，麻烦数变为了 $(0, 0, 0, 0, 0, 0)$。

一共 $5$ 次操作。

数据范围与提示

• 子任务 1（30 分）：保证 $a_i = 1$，即所有史莱姆体重都是 $1$。
• 子任务 2（30 分）：保证 $a_i = i$，$m = n - 1$，$u_i = i$，$v_i = i + 1$。
• 子任务 3（40 分）：无特殊限制。
• 对于 $100\%$ 的数据：$5 \le n \le 5000$，$1 \le m \le \min\left\{\dfrac{n(n-1)}{2}, 5000\right\}$，$1 \le u_i, v_i \le n$，$u_i \ne v_i$，保证不存在重复的朋友关系，$1 \le a_i \le 5000$，$0 \le b_i \le 10^9$。