Bluewater Geocloud Organization (BGO) 最近开发了一款全新的软件，能够以极高的精度预测任何特定云层开始和停止降雨的秒数，以及降雨的强度。然而，云层的移动存在一定的不确定性；对于每个邮政编码区域，每朵云以一定的概率出现在该区域上空。

你从 BGO 网站上获取了关于你所在邮政编码区域的一些信息，并希望利用这些信息来规划前往公交车站的路线。你希望最小化你所受到的预期降雨量。为了赶上公交车，你必须在从现在起 $t$ 秒内到达公交车站。你测得自己的步行速度恰好为 $1\,\text{m/s}$。

更复杂的是，前往公交车站的路上部分路段有屋顶覆盖，在这些地方，你或许可以通过短暂停留来避开最强烈的降雨。你的家门口（距离公交车站 $d$ 米）总是在屋顶之下，但公交车站不一定。

输入格式

第一行包含四个空格分隔的整数：$d$ ($1 \le d \le 1\,000$)，表示到公交车站的距离（单位：米）；$t$ ($d \le t \le 10\,000$)，表示公交车出发的时间；$c$ ($0 \le c \le 1\,000\,000$)，表示 BGO 追踪的云层数量；以及 $r$ ($0 \le r \le d$)，表示屋顶的数量。接下来的 $c$ 行描述云层；第 $i$ 行包含四个数字 $s_i, e_i, p_i$ 和 $a_i$，描述第 $i$ 朵云：

• $s_i$ ($0 \le s_i < t$) 是一个整数，表示云层开始降雨的秒数；
• $e_i$ ($s_i < e_i \le t$) 是一个整数，表示云层结束降雨的秒数；
• $p_i$ ($0 \le p_i \le 1$) 是一个实数（小数点后最多 6 位），表示该云层在其降雨期间出现在你所在邮政编码区域的概率；
• $a_i$ ($0 \le a_i \le 100$) 是一个整数，表示该云层在降雨期间释放的降雨量，单位为 $\text{nm/s}$。

最后 $r$ 行描述屋顶路段，每行包含两个整数 $x_j$ 和 $y_j$ ($0 \le x_j < y_j \le d + 1$)，表示一段屋顶，从距离家 $x_j$ 米处开始，到距离家 $y_j$ 米处结束。你的家、公交车站以及它们之间的整条路线都在同一个邮政编码区域内。没有两个屋顶重叠，但一个屋顶的起点可能与另一个屋顶的终点重合。

输出格式

输出一个实数，表示如果你能在规定时间内到达公交车站，你所受到的预期降雨量的最小值（单位：$\text{nm}$）。如果答案与标准答案的绝对误差或相对误差不超过 $10^{-5}$，则视为正确。

样例

样例输入 1

20 60 2 1
5 15 0.33333 30
22 60 0.66666 70
0 10

样例输出 1

466.662

样例输入 2

3 4 2 1
1 3 0.25 8
2 4 0.66667 15
1 2

样例输出 2

10.00005

样例输入 3

3 4 1 0
0 2 0.25 8

样例输出 3

2.0

样例输入 4

3 5 2 1
0 3 0.125 32
2 5 0.5 32
3 4

样例输出 4

28.0