P4926 [1007] Double-Kill Meter

Today, Scarlet was lucky enough to witness a unique OI training session in the computer lab. Because of some strange SPJ, every contestant’s score in the contest was a positive real number (and it even has no upper limit). When contestant A’s score is at least $k$ ($k>0$) times contestant B’s score, we say contestant A **$k$-double-killed** contestant B, and contestant B **was $k$-double-killed** by contestant A. Even more strangely (and more excitingly), before the training, many contestants made Flags such as “If I don’t $k$-double-kill contestant X, I’ll eat something good,” or “If contestant Y $k$-double-kills me, I’ll eat something good.” Coach Patchouli, who knows the truth and still has a conscience, in order to keep order in the lab and avoid people eating too well and hurting their health, relaxed the Flag requirements. Patchouli set a **positive** constant $T$. A contestant who made the Flag “If I don’t $k$-double-kill contestant X, I’ll eat something good” will not need to eat something good as long as they successfully $k-T$-double-kill contestant X. Similarly, a contestant who made the Flag “If contestant Y $k$-double-kills me, I’ll eat something good” will not need to eat something good as long as they are not successfully $k+T$-double-killed by contestant Y. Scarlet, who already knows the scores of some contestants and the exact Flags, really cannot bear to see such a wonderful contest end with nobody eating something good. To make it easier to negotiate with Patchouli, Scarlet wants to determine the largest real number $T$ such that, after the contest, there will definitely be at least one contestant who has to fulfill their Flag and eat something good.

The first line contains three integers $n,s,t$, representing the number of contestants in the lab, the total number of Flags made by contestants, and the number of contestants’ scores known by Scarlet. The $n$ contestants are numbered from $1$ to $n$. The contestant with number $k$ is called contestant $k$. The next $s$ lines each contain four integers $o,A,B,k$. Here, $o=1$ means contestant A made the Flag “If I don’t $k$-double-kill contestant B, I’ll eat something good,” and $o=2$ means contestant A made the Flag “If contestant B $k$-double-kills me, I’ll eat something good.” The next $t$ lines each contain two integers $C,x$, meaning Scarlet knows that contestant $C$ has score $x$.

If there exists a largest $T$ that can guarantee that, after the contest, there will be a contestant who eats something good, output $T$. Your output is considered correct if the absolute error from the answer does not exceed $10^{-4}$. If it does not exist, output `-1`.

- For $30\%$ of the testdata, $n\leq 5$, $s\leq 2$. - For another $40\%$ of the testdata, it is guaranteed that $t=n$. - For $100\%$ of the testdata, $1\leq n,s\leq 1000$, $1\leq A,B,C,t\leq n$, $1\leq k\leq 10$, $1\leq x\leq 10^9$. It is guaranteed that all input $C$ are pairwise distinct. Translated by ChatGPT 5