Maximizing the Chat Group Ratio

In the chat group called "Improving Life", there are a total of $n$ topics numbered from $1$ to $n$, and $n$ members (member $1$ is Xiao Z, and members $2$ through $n$ are his friends). Each topic $i$ is associated with a member $c_i$ (which could be Xiao Z himself, i.e. $c_i=1$) and if the topic appears in the chat, the interested member will engage in an intense discussion lasting $w_i$ minutes. Furthermore, there are $m$ guiding relations between topics. Each guiding relation is given as a pair $(u,v)$ meaning that if topic $u$ appears, then topic $v$ will definitely appear.

Since all of Xiao Z’s different topics (those with $c_i=1$) have no direct or indirect guiding relations among themselves, Xiao Z can choose to initiate one or more topics he is interested in (i.e. topics with $c_i=1$). Note that for any topic with $c_i\neq1$, its appearance can only be triggered via a guiding relation. Once a topic is initiated, the chain of guidance will force its entire closure (i.e. all topics reachable via the guiding relations) to appear (each topic appears at most once even if triggered from multiple sources).

Let $\mathrm{sum}(k)$ denote the total minutes of intense discussion by member $k$ (i.e. the sum of $w$ values for all appeared topics that member $k$ is interested in). Xiao Z wants to choose a nonempty subset of his own topics to initiate so that the ratio

[ R = \frac{\max\limits_{k=2}^{n} \mathrm{sum}(k)}{\mathrm{sum}(1)} ]

is as large as possible. Your task is to help him compute the maximum possible value of ( R ) (and output its value after taking the floor). In other words, among all valid choices of initiated topics (which must be among those with $c_i=1$), compute the closure of each chosen set, then calculate (\mathrm{sum}(1)) (the total minutes by Xiao Z) and, for each friend $k\ge2$, (\mathrm{sum}(k)) (the total minutes by friend $k$). Then, let the ratio be the maximum over $k\ge2$ of (\mathrm{sum}(k)/\mathrm{sum}(1)). Output the floor of the maximum ratio that can be achieved.

All formulas are given in (\LaTeX) format. You can assume that every topic (even if appeared more than once via different chains) is only counted once. Also, note that if no topic of a friend appears, then his discussion time is considered as $0$.

inputFormat

The first line contains two integers $n$ and $m$, where $n$ is the number of topics (and also the number of group members) and $m$ is the number of guiding relations. The following $n$ lines each contains two integers $c_i$ and $w_i$, indicating that topic $i$ is interesting to member $c_i$ and carries a weight of $w_i$ minutes for intense discussion. The next $m$ lines each contains two integers $u$ and $v$, representing a guiding relation: if topic $u$ appears then topic $v$ will definitely appear.

outputFormat

Output a single integer, which is the maximum possible value (after taking the floor) of the ratio (R = \frac{\max_{k=2}^n \mathrm{sum}(k)}{\mathrm{sum}(1)}) that Xiao Z can achieve by initiating an appropriate nonempty subset of his own topics.

sample

3 1
1 3
2 4
1 2
1 2

1