Extra
Time
聪明的质检员 Time:1s Memory:50M AC:14% Submit:37


【问题描述】
小T 是一名质量监督员,最近负责检验一批矿产的质量。这批矿产共有n个 矿石,从1到n逐一编号,每个矿石都有自己的重量wi以及价值vi。检验矿产的 流程是:
1.  给定m个区间[Li,Ri];
2. 选出一个参数W ;
3.  对于一个区间[Li,Ri],t算矿石在这个区间上的检验值Yi:

Y_i= \sum_{j}1\times \sum _{j}v_j,j\in [L_i,R_i],w_j\geqslant W

这批矿产的检验结果Y为各个区间的检验值之和。即:
Y=\sum_{i=1}^{m}Yi
若这批矿产的检验结果与所给标准值S相差太多,就需要再去检验另一批
矿产。小T 不想费时间去检验另一批矿产,所以他想通过调整参数W 的值,让 检验结果尽可能的靠近标准值S即使得S − Y 的绝对值最小,请你帮忙求出这 个最小值。
【输入】
输入文件为qc.in。
第一行包含三个整数n,  m,  S,分别表示矿石的个数、区间的个数和标准
值。
接下来的n 行,每行2  个整数,中间用全格隔开,第i + 1  行表示i 号矿石
的重量wi 和价值vi 。
接下来的m 行,表示区间,每行2 个整数,中间用全格隔开,第i + n + 1
行表示区间[Li, Ri]的两个端点Li   和Ri。注意:不同区间可能重合或相互重叠。
【输出】
输出文件为qc.out。 输出只有一行,包含一个整数,表示所求的最小值。

【输入输出样例】
qc.in                                                qc.out
5 3 15                                                 10
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3
5

【样例解释】
当W 选4 的时候,三个区间上检验值分别为20、5、0,这批矿产的检验结
果为25,此时与标准值S 相差最小为10。
搬运者注:Yi表示所有满足题意的j的个数× 所有满足题意的j的vj 。
【数据范围】
对于10%的数据,有1 ≤ n, m ≤ 10; 对于30%的数据,有1 ≤ n, m ≤ 500; 对于50%的数据,有1 ≤ n, m ≤ 5000; 对于70%的数据,有1 ≤ n, m ≤ 
10000;
对于100%的数据, 有1  ≤ n, m ≤ 200000, 0  < wi, vi  ≤ 106, 0  < S  ≤
1012, 1 ≤ Li ≤ Ri ≤ n。
6