题目描述

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

1. 给定 $m$ 个区间 $[l_i,r_i]$；
2. 选出一个参数 $W$；
3. 对于一个区间 $[l_i,r_i]$，计算矿石在这个区间上的检验值 $y_i$：

$$y_i=\sum\limits_{j=l_i}^{r_i}[w_j \ge W] \times \sum\limits_{j=l_i}^{r_i}([w_j \ge W] \times v_j)$$

这批矿产的检验结果 $y$ 为各个区间的检验值之和。即：$y = \sum\limits_{i=1}^m y_i$。

若这批矿产的检验结果 $y$ 与所给标准值 $s$ 相差太多，就需要再去检验另一批矿产。小 T 不想费时间去检验另一批矿产，所以他想通过调整参数 $W$ 的值，让检验结果尽可能的靠近标准值 $s$，即使得 $|s-y|$ 最小。请你帮忙求出这个最小值。

$[p]$：称为指示函数（或艾弗森括号），若括号内的条件 $p$ 为真则返回 $1$，否则返回 $0$。例如 $[w_j \ge W]$ 表示当第 $j$ 个矿石的重量大于等于 $W$ 时值为 $1$，否则为 $0$。

$\sum$：求和符号。例如 $\sum_{j=l_i}^{r_i}$ 表示对下标 $j$ 从 $l_i$ 递增到 $r_i$ 这一范围内的所有对应项进行相加。因此公式中前半部分表示区间内重量大于等于 $W$ 的矿石个数，后半部分表示区间内重量大于等于 $W$ 的矿石价值总和。

$|s-y|$：绝对值符号，表示 $s$ 与 $y$ 两数之差的绝对大小（非负值）。

输入格式

第一行包含三个整数 $n,m,s$ —— 分别表示矿石的个数、区间的个数和标准值。

接下来的 $n$ 行，每行包含两个整数 $w_i, v_i$ —— 其中第 $i$ 行表示 $i$ 号矿石的重量和价值。

接下来的 $m$ 行，每行包含两个整数 $l_i, r_i$ —— 其中第 $i$ 行表示第 $i$ 个区间 $[l_i,r_i]$ 的两个端点。注意：不同区间可能重合或相互重叠。

输出格式

输出一行，一个整数，表示使得 $|s-y|$ 达到最小的那个最小值。

样例输入 1

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

样例输出 1

10

说明

样例解释

当参数 $W$ 选 $4$ 的时候：

• 对于第 $1$ 个区间 $[1, 5]$，重量大于等于 $4$ 的矿石有 $4$ 号和 $5$ 号（共 $2$ 个），价值和为 $5 + 5 = 10$，检验值 $y_1 = 2 \times 10 = 20$；
• 对于第 $2$ 个区间 $[2, 4]$，重量大于等于 $4$ 的矿石只有 $4$ 号（共 $1$ 个），价值和为 $5$，检验值 $y_2 = 1 \times 5 = 5$；
• 对于第 $3$ 个区间 $[3, 3]$，没有重量大于等于 $4$ 的矿石，检验值 $y_3 = 0 \times 0 = 0$。

这批矿产的检验结果 $y = 20 + 5 + 0 = 25$。此时与标准值 $s=15$ 相差为 $|15-25|=10$。可以证明，没有比 $10$ 更小的差值。

数据范围

• 对于 $10\%$ 的数据，保证 $1 \le n,m \le 10$；
• 对于 $30\%$ 的数据，保证 $1 \le n,m \le 500$；
• 对于 $50\%$ 的数据，保证 $1 \le n,m \le 5000$；
• 对于 $70\%$ 的数据，保证 $1 \le n,m \le 10000$；
• 对于 $100\%$ 的数据，保证 $1 \le n,m \le 2\times 10^5$，$0 < w_i, v_i \le 10^6$，$0 < s \le 10^{12}$，$1 \le l_i \le r_i \le n$。
• 保证所有的输入数值均为整数。