Problem Description

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.

Input Format

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

Output Format

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.

3 5 1
1 2 1 2
1 3 2 2
1 3 1 4
2 1 2 2
2 1 3 4
1 1

-1

3 2 3
1 2 1 10
2 2 3 6
1 1
2 6
3 9

3.9999993984

Hint

• 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