P5382 [THUPC 2019] Improve Life

"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.

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 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.

### 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 . Translated by ChatGPT 5