题目描述

小 $\red{T}$ 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 $\red{n}$ 个矿石，从 $\red{1}$ 到 $\red{n}$ 逐一编号，每个矿石都有自己的重量 $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_j1 \cdot \sum_j{v_j}，\space j\in[L_i,R_i]}且\space\space\red{ w_j\geq W}，\space\red{ j}是\space\space 矿\space\space石\space\space编\space\space号$$

这批矿产的检验结果 Y 为各个区间的检验值之和。即：$\red{Y=\sum_{i=1}^m{Y_i}}$

若这批矿产的检验结果与所给标准值 $\red{S}$ 相差太多，就需要再去检验另一批矿产。

小 $\red{T}$ 不想费时间去检验另一批矿产，所以他想通过调整参数 $\red{W}$ 的值，让检验结果尽可能的靠近 标准值 $\red{S}$，即使得 $\red{|S-Y|}$ 最小。请你帮忙求出这个最小值。

输入格式

输入文件 $\red{qc.in}$ 。

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

接下来的 $\red{n}$ 行，每行 $\red{2}$ 个整数，中间用空格隔开，第 $\red{i+1}$ 行表示 $\red{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}$ 。

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

输出格式

输出文件名为 $\red{qc.out}$ 。

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

样例

样例输入

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

样例输出

10

样例说明

当 $\red{W}$ 选 $\red{4}$ 的时候，三个区间上检验值分别为 $\red{20}$ 、 $\red{5}$ 、 $\red{0}$ ，这批矿产的检验结果为 $\red{25}$ ，此时与标准值 $\red{S}$ 相差最小为 $\red{10}$ 。

数据范围与提示

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

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

对于$\red{50\%}$ 的数据，有 $\red{n，m\leq5,000}$；

对于$\red{70\%}$ 的数据，有 $\red{n，m\leq10,000}$；

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