问题描述

小 T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有$\red n$个矿石，从 $\red{1}$ 到$\red n$逐一编号，每个矿石都有自己的重量$\red{w_i}$以及价值$\red{v_i}$。检验矿产的流程是：

1. 给定 $\red{m}$个区间$\red{[L_i, R_i]}$；

2. 选出一个参数$\red{W}$；

3. 对于一个区间$\red{[L_i, R_i]}$，计算矿石在这个区间上的 检验值$\red{Y_i}$ ： $\red{[Y_i = \sum_j 1 \times \sum_j v_j , j \in [L_i, R_i]}$ 且$\red{w_j \ge W, j}$是矿石编号。 这批矿产的 检验结果$\red{Y}$为各个区间的检验值之和 。即： $\red{[ Y = \sum_{i=1}^{m} Y_i ]}$ 若这批矿产的检验结果与所给标准值 $\red{S}$ 相差太多，就需要再去检验另一批矿产。小 T 不想费时间去检验另一批矿产，所以他想通过调整参数 $\red{W}$ 的值，让检验结果尽可能的靠近标准值 $\red{S}$，即使得$\red{S-Y}$的绝对值最小。请你帮忙求出这个最小值。

输入格式

第一行包含三个整数$\red{n，m，S}$，分别表示矿石的个数、区间的个数和标准值。

接下来的$\red{n}$ 行，每行$\red{2}$ 个整数，中间用空格隔开，第$\red{i+1 }$行表示i 号矿石的重量$\red{w_i }$和价值$\red{v_i}$ 。

接下来的$\red{m}$ 行，表示区间，每行$\red{2}$ 个整数，中间用空格隔开，第$\red{i+n+1 }$行表示区间$\red{[L_i,R_i]}$的两个端点$\red{L_i }$和$\red{R_i}$。

注意：不同区间可能重合或相互重叠。

输出格式

输出只有一行，包含一个整数，表示所求的最小值。

样例

输入样例

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

输出样例

10

提示

对于$\red{10\%}$的数据，有$\red{1≤n，m≤10}$；

对于$\red{30\%}$的数据，有$\red{1≤n，m≤500}$；

对于$\red{50\%}$的数据，有$\red{1≤n，m≤5000}$；

对于$\red{70\%}$的数据，有$\red{1≤n，m≤10000}$；

对于$\red{100\%}$的数据，有$\red{1≤n，m≤200000，0 < w_i, v_i≤10^6，0 < S≤10^{12}，1≤L_i≤R_i≤n}$。