Description

"Improve Life" is a group chat created by Xiao Z. In the group chat, Xiao Z and his $n-1$ friends (there are $n$ members in total; Xiao Z is numbered $1$, and his friends are numbered from $2$ to $n$) talk about everything and have a great time. However, chatting too much is often labeled as being the "chat king", which gives Xiao Z a headache.

Today, Xiao Z foresees that there may be $n$ topics in the group (numbered from $1$ to $n$). Topic $i$ is a topic that member $c_i$ (possibly Xiao Z himself) is interested in. This means that if this topic appears, this member will make an intense speech for $w_i$ minutes. For convenience, you may assume that apart from this, members will not make intense speeches.

Among all $n$ topics, there are $m$ guiding relationships. Each guiding relationship is an ordered pair $\left(u,v\right)$, meaning that if topic $u$ appears, it will definitely cause topic $v$ to appear.

Coincidentally, Xiao Z发现 that among all of his own different topics, there is no direct or indirect guiding relationship.

Because the midterm exams are coming, all members except Xiao Z are busy studying, so they will not proactively start topics (starting a topic means making a topic appear; same below). That is, all topics with $c_i\neq 1$ can only be triggered directly or indirectly by guiding relationships. This puts Xiao Z in a dilemma: he wants to chat a lot, but also wants to get rid of the "chat king" label. Therefore, he decides to proactively start one or more topics that he is interested in, to induce other topics to appear, so that the ratio of the maximum intense speaking time among other members to Xiao Z's own intense speaking time is as large as possible. That is, maximize the following expression:

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

Here, $\text{sum}\left(k\right)$ denotes the sum of $w$ values over all topics that appear and that member $k$ is interested in.

To avoid precision errors, you only need to output the result of rounding down the maximum value.

Input Format

The first line contains two positive integers $n,m$, representing the number of topics (which is also exactly the number of group members) and the number of guiding relationships.

The second line contains $n$ positive integers $c_1,\dots, c_n$ ($1\leq c_i\leq n$), describing the member number who is interested in each topic in order. It is guaranteed that there exists at least one $i$ such that $c_i=1$.

The third line contains $n$ positive integers $w_1,\dots, w_n$ ($1\leq w_i\leq 100$), describing the time of intense speech for the member interested in each topic.

The next $m$ lines describe the guiding relationships. Each line contains two positive integers $u,v$ ($1\leq u,v\leq n$), describing a guiding relationship $\left(u,v\right)$. See the Description for the exact meaning. It is guaranteed that between any two different topics with $c_i=1$, there is neither a direct nor an indirect guiding relationship.

For each line, if it contains multiple numbers, they are separated by a single space.

Constraints: $1\leq n\leq 700$, $1\leq m\leq 60000$.

Output Format

Output a single integer on one line: the result of rounding down the maximum value of the required expression, i.e., the largest integer not exceeding that value.

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

Hint

Sample Explanation

Xiao Z can choose to start topics numbered 3 and 4. This will cause topics numbered 5, 6, and 7 to appear, and trigger an intense speech of $150$ minutes by member 3, and $40$ minutes by member 4. Since member 3 speaks for a longer time, and Xiao Z's own intense speaking time is $60$ minutes, the maximum ratio is $\frac{150}{60}=2.5$, and rounding it down gives $2$.

It can be proven that Xiao Z has no better strategy.

Copyright Information

From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2019.

Resources such as solutions can be found at https://github.com/wangyurzee7/THUPC2019.

Translated by ChatGPT 5