You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $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$ 次操作。

数据规模与约定

对于 $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 分）：没有特殊限制。