[1007]倍杀测量者

题目描述

今天Scarlet在机房有幸目睹了一场别开生面的OI训练。因为一些奇妙的SPJ,比赛中所有选手的得分都是正实数(甚至没有上限)。 当一位选手A的分数不小于选手B的分数$k$($k>0$)倍时,我们称选手A**“$k$倍杀”**了选手B,选手B**被**选手A**“$k$倍杀”**了 更奇妙也更激动人心的是,训练前有不少选手立下了诸如“我没$k$倍杀选手X,我就女装”,“选手Y把我$k$倍杀,我就女装”的Flag。 知道真相的良心教练Patchouli为了维持机房秩序,放宽了选手们的Flag限制。Patchouli设定了一个**正**常数$T$,立下“我没$k$倍杀选手X就女装”的选手只要成功$k-T$倍杀了选手X,就不需要女装。同样的,立下“选手Y把我$k$倍杀我就女装”的选手只要没有成功被选手Y$k+T$倍杀,也不需要女装。 提前知道了某些选手分数和具体Flag的Scarlet实在不忍心看到这么一次精彩比赛却没人女装,为了方便和Patchouli交易,Scarlet想要确定最大的实数$T$使得赛后一定有选手收Flag女装。

输入输出格式

输入格式


第一行三个整数$n,s,t$,分别表示机房内选手人数,选手立下的Flag总数和Scarlet已知的选手分数的数量。$n$位选手从$1$开始编号至$n$,编号为$k$的选手被称为选手$k$。 接下来$s$行,每行四个整数$o,A,B,k$。其中$o=1$表示选手A立下了“我没$k$倍杀选手B就女装”的Flag,$o=2$表示选手A立下了“选手B把我$k$倍杀我就女装”的Flag。 接下来$t$行,每行两个整数$C,x$,表示Scarlet已知选手C的分数为$x$

输出格式


若存在能保证赛后有选手女装的最大的T,则输出T,只有当输出与答案的绝对误差不超过$10^{-4}$时才被视作正确输出。 若不存在,输出"-1"(去掉引号)

输入输出样例

输入样例 #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

-1

输入样例 #2

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

输出样例 #2

3.9999993984

说明

对于30%的数据,$1\leq n\leq5,1\leq s\leq 2$ 对于另40%的数据,保证$t=n$ 对于100%的数据,$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$。保证输入中的$C$两两不同。