问题描述

阿福是魔法学院的资深符文师。学院最近发明了一台“符文能量检测仪”，用来分析古代符文石的能量场。

检测仪扫描廊道中依次排列着 $n$ 块符文石，每块石头 $i$ 拥有：能量密度 $e_i$以及魔力值 $m_i$ 检测仪的工作方式如下： 设定一个能量密度基准线 $W$

对于每个待检测的符文段 $[L_i, R_i]$，仪器会扫描其中的每一块石头 $j$ $(L_i \le j \le R_i)$ 只有能量密度 $e_j \ge W$ 的符文石才会被激发。 该符文段的共振强度计算为： $Y_i$=(该段被激发的符文石数量)×(该段所有被激发石头的魔力值总和) 仪器对 $m$ 个指定的符文段进行检测，将每个段的共振强度 $Y_i$ 相加，得到总共振值 $S$：

​阿福的任务 根据古籍记载，目标总共振值应该是 $T$。阿福需要通过调整能量密度基准线 $W$，让实际检测到的总共振值 $S$ 尽可能接近目标 $T$，即最小化 $|S - T|$。

请计算这个最小的 $|S - T|$。

Format

Input

第一行：$n, q, T$（符文石数量、检测段数、目标共振值）

接下来 $n$ 行：每行 $e_i, m_i$（每块石头的能量密度和魔力值）

接下来 $m$ 行：每行 $L_i, R_i$（每个检测段的起止位置）

Output

输出最小化的 $|S - T|$

Samples

5 3 20
4 2
3 1
6 3
2 1
5 4
1 5
2 3
3 4

2

当 W=4 时：三个区间上魔力和分别为 20,5,0，总共振值为 25，与目标总共振值 T相差最小为 10。

Limitation

数据范围 $1 \le n, q \le 200,000$

$0 < e_i, m_i \le 10^6$

$0 < T \le 10^{12}$

$1 \le L_i \le R_i \le n$