/ Vijos / 题库 /

聪明的质检员

聪明的质检员

描述

小 T 是一名质量监督员,最近负责检验一批矿产的质量。这批矿产共有n个矿石,从1到n逐一编号,每个矿石都有自己的重量wi以及价值vi。检验矿产的流程是:
1、给定m个区间[Li,Ri];
2、选出一个参数W;
3、对于一个区间[Li,Ri],计算矿石在这个区间上的 检验值Yi
\( Y_i = (\sum\limits_j 1) * (\sum\limits_j v_j) , j \in [L_i,R_i]\) 且 \(w_j \ge W \)
j是矿石编号

这批矿产的 检验结果Y 为各个区间的检验值之和 。即:\(Y = \sum\limits_{i=1}^m Y_i\)
若这批矿产的 检验结果 与所给标准值S相差太多,就需要再去检验另一批矿产。小T不想费时间去检验另一批矿产,所以他想通过调整参数W的值,让 检验结果 尽可能的靠近标准值S,即使得 S-Y 的绝对值最小。请你帮忙求出这个最小值。

格式

输入格式

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

接下来的n行,每行2个整数,中间用空格隔开,第i+1行表示i号矿石的重量wi和价值vi 。

接下来的m行,表示区间,每行2个整数,中间用空格隔开,第i+n+1行表示区间[Li,Ri]的两个端点Li和Ri。 注意:不同区间可能重合或相互重叠。

输出格式

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

样例1

样例输入1

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

样例输出1

10

限制

1s

提示

样例说明:当W选4的时候,三个区间上检验值分别为20、5、0,这批矿产的检验结果为25,此时与标准值S相差最小为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 < wi, vi ≤ 10^6,0 < S ≤ 10^12,1 ≤ Li ≤ Ri ≤ n。

来源

NOIp2011提高组Day2第二题

信息

ID
1740
难度
7
分类
其他 | 二分查找 点击显示
标签
递交数
4082
已通过
849
通过率
21%
被复制
12
上传者

相关