该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

题目描述

当你做到这题的时候，D老师的台风监测系统已经发展到了5.0AI防御版本了。现D老师生产了 $n$ 套5.0版本的台风监测系统-代号飞廉，并编号为 $1\sim n$。这些飞廉系统分别布置在了$n$个城市，且他们之间有 $m$ 对信号链接关系，第 $i$ 对链接关系用 $u_i,v_i$ 描述，表示编号为 $u_i$ 和 $v_i$ 的飞廉系统可以互相通信。（没有直接链接的飞廉系统之间不能互相通信）。

另外每个飞廉系统都有一个功率属性，第 $i$ 套飞廉系统的功率为 $a_i$。

每套飞廉还有它自己的抗台风等级，第 $i$ 套飞廉的初始抗台风等级为 $b_i$。

台风的运行轨迹是随时变化莫测，为了更好的应对“桦加沙”号台风，D老师必须在台风到来之前完成系统测试。现在D老师想让你帮他完成这套系统的调试，你可以完成若干次操作，每次操作包含下面两个步骤：

1. 先选择第$x$号功率不为 $0$ 的飞廉，该套系统可以发信号给和他有直接链接信号的下一级飞廉系统，使得收到信号的飞廉的抗台风系数值增加$1$，但是第$x$号飞廉系统本身的抗台风系数会减少 $1$。
2. 你可以挑选和第一步中选择的$x$号飞廉系统直接相链接的一个或多个飞廉系统，但必须满足这些下级飞廉系统的功率之和小于$x$号飞廉系统的功率，然后可以让这些被选中的下级飞廉系统的抗台风系数值增加 $1$。如果无法找到满足条件的下级飞廉系统，可以不做这一步。

为了尽可能的更多测试系统，现在你的任务是需要尽可能多的进行操作，D老师让你求出最多能进行多少次操作（题目保证能在有限次操作后结束）。

输入格式

第一行为空格隔开的两个整数：$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

样例解释

• 初始6套飞廉系统的抗台风等级系数初始值分别为 $(1,0,0,0,0,1)$。
• 先选择第 $6$ 号飞廉系统，其功率值为9，抗台风等级值为1，然后给和他链接的 $5,4$ 号（他们的功率之和为$3+2<9$)飞廉系统的抗台风系数值加 $1$，但是第$6$号飞廉其自身的抗台风等级值会-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$ 次系统测试操作。

数据规模与约定

对于 $100\%$ 的数据：

• $5 \le n \le 5000$，$1\le m\le \min\{\frac{n(n-1)}{2},5000\}$
• $1\le u_i,v_i\le n$，$u_i\neq v_i$，保证不存在重复的 $u_i,v_i$。
• $1\le a_i\le 5000$，$0\le b_i\le 10^9$

子任务划分：

• 子任务 1（30 分）：保证 $a_i=1$。即所有飞廉系统的功率都是 $1$。
• 子任务 2（30 分）：保证 $a_i=i$，$m=n-1$，$u_i=i$，$v_i=u_i+1$。
• 子任务 3（40 分）：没有特殊限制。