OpenJudge

1:聪明的质监员

总时间限制:
20000ms
单个测试点时间限制:
1000ms
内存限制:
128000kB
描述

输入
第一行包含三个整数 n,m,S,分别表示矿石的个数、区间的个数和标准值。
接下来的 n 行,每行 2 个整数,中间用空格隔开,第 i+1 行表示 i 号矿石的重量 w i 和价
值 v i 。
接下来的 m 行,表示区间,每行 2 个整数,中间用空格隔开,第 i+n+1 行表示区间[L i ,
R i ]的两个端点 L i 和 R i 。
输出
输出只有一行,包含一个整数,表示所求的最小值。
样例输入
5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3
样例输出
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 < w i , v i ≤10 6 ,0 < S≤10 12 ,1≤L i ≤R i ≤n。
来源
NOIP2011
全局题号
11195
添加于
2016-08-14
提交次数
4
尝试人数
2
通过人数
2