[THUPC2019] 改善生活

题目描述

「改善生活」是小 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$。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

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> 查看。