题目描述

「改善生活」是小 Z 创建的一个群聊。在群聊里，小 Z 和他的 $n-1$ 个朋友们（共 $n$ 名群友，小 Z 的编号为 $1$，他的朋友们的编号从 $2$ 至 $n$）无话不说，畅谈甚欢。然而，经常水群会被冠以水王的名号，这让小 Z 头痛不已。

今天，小 Z 预见到了群里可能会有 $n$ 个话题（编号从 $1$ 至 $n$）。其中，第 $i$ 个话题是 $c_i$ 号群友（当然也有可能是小 Z 自己）感兴趣的话题，这意味着该话题如果出现，这位群友将会进行 $w_i$ 分钟的激烈发言。方便起见，你可以认为，除此之外，群友不会进行激烈发言。

所有 $n$ 个话题之间有 $m$ 组引导关系，每组引导关系的形式是一个二元组 $\left(u,v\right)$，它表示如果 $u$ 号话题出现，必定会导致 $v$ 号话题出现。

巧合的是，小 Z 发现，所有他自己的不同话题都不存在直接或间接的引导关系。

由于期中考试的临近，除小 Z 外的群友们都忙于复习，因此他们不会主动发起话题（发起话题指让一个话题出现，下同），也就是说，所有 $c_i\neq 1$ 的话题都只能由引导关系直接或间接引出。这让想要水群、却又希望摆脱水王名号的小 Z 左右为难。因此，他决定主动发起一个或以上的自己感兴趣的话题，来诱导其他话题的出现，致使水群最多的另一位群友激烈发言的时间与小 Z 自己激烈发言的时间的比值尽可能大。即最大化下面这个式子：

$$\frac{\max\limits_{k=2}^n \text{sum}\left(k\right)}{\text{sum}\left(1\right)} $$

其中，$\text{sum}\left(k\right)$ 表示所有出现且群友 $k$ 感兴趣的话题的 $w$ 值总和。

为避免精度误差，你只需要求出最大值向下取整的结果即可。

输入格式

第一行两个正整数 $n,m$，分别表示话题数（恰好也是群人数）、引导关系组数。

第二行 $n$ 个正整数 $c_1,\dots, c_n$（$1\leq c_i\leq n$），依次描述对各话题感兴趣的群友编号。保证至少存在一个$i$ 使得 $c_i=1$。

第三行 $n$ 个正整数 $w_1,\dots, w_n$（$1\leq w_i\leq 100$），依次描述各话题感兴趣的群友将激烈发言的时间。

接下来 $m$ 行描述引导关系，每行两个正整数 $u,v$（$1\leq u,v\leq n$），描述一组引导关系 $\left(u,v\right)$，具体意义见【题目描述】，保证所有不同的 $c_i=1$ 的话题之间两两不存在直接或间接的引导关系。

对于每一行，如果行内包含多个数，则用单个空格将它们隔开。

保证 $1\leq n\leq 700$，$1\leq m\leq 60000$。

输出格式

一行一个整数，表示所求式子最大值向下取整的结果，即不超过该值的最大整数。

7 8
2 2 1 1 3 3 4
100 100 40 20 100 50 40
1 3
2 3
1 4
2 4
3 5
4 6
3 7
4 7

2

提示

样例解释

小 Z 可以选择发起编号为 3 和 4 的话题，这将致使编号为 5、6、7 的话题出现，并引发 3 号群友时长 $150$ 分钟的激烈发言、以及 4 号群友时长 $40$ 分钟的激烈发言。由于 $3$ 号群友激烈发言时间更长，且小 Z 自己的激烈发言时长为 $60$ 分钟，因此所求最大比值为 $\frac{150}{60}=2.5$，这个值向下取整的结果是 $2$。

可以证明小 Z 不存在更优的策略。

版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。