该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

题目描述

有一批零件共 $N$ 个，编号为 $1$ ~ $N$。零件 $i$ 的体积是 $V_i$，重量是 $W_i$。

现在要对这批零件进行质检，流程如下：

• 1、设置一个参数 $P$
• 2、设定 $M$ 个区间
• 3、对设定的每一个区间 $[A_i, B_i]$ 内的零件进行检测，该区间的检测结果为

$q_i =[\sum\limits_{k=A_i}^{B_i}(V_k ≥ P ? 1:0)] × [\sum\limits_{k=A_i}^{B_i}((V_k ≥ P? 1:0)×W_k)]$，其中 $k$ 是零件编号

• 4、该批零件的最终检测结果 $Q = \sum\limits_{i=1}^M q_i$

现在想要通过调整 $P$ 的值，使得 $Q$ 尽可能接近标准值 $T$，即使得 $D=|Q-T|$ 的值尽可能小。

请你求出 $D$ 的最小值。

输入格式

第一行：$N, M, T$；

接下来 $N$ 行，每行两个整数 $V_i, W_i$；

接下来 $M$ 行，每行两个整数 $A_i, B_i$。区间可以重合或重叠。

输出格式

一个整数，表示 $D$ 的最小值。

样例输入

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

样例输出

10

样例说明

当设置参数 $P=4$ 时，三个区间 $[1, 5]、[2, 4]、[3, 3]$ 的检测结果依次为 $q_1=20, q_2=5, q_3=0$ ，最终检测结果 $Q=q_1+q_2+q_3=25$，此时 $D=|Q-T|=10$ 为最小。

数据范围

对于 $10\%$ 的数据，有 $1 ≤ N, M ≤ 10$；

对于 $30\%$的数据，有 $1 ≤ N, M ≤ 500$ ；

对于 $50\%$ 的数据，有 $1 ≤ N, M ≤ 5,000$；

对于 $70\%$ 的数据，有 $1 ≤ N, M ≤ 10,000$ ；

对于 $100\%$ 的数据，有 $1 ≤ N, M ≤ 200,000$，$0 < V_i, W_i ≤ 10^6$，$0 < T ≤ 10^{12}$，$1 ≤ A_i ≤ B_i ≤ N$ 。