问题 2984 --D22 聪明的质监员

2984: D22 聪明的质监员

时间限制: 1 Sec  内存限制: 128 MB
提交: 13  解决: 8
[提交][状态][讨论版][命题人:]

题目描述

有个质量监督员负责检查矿石质量。 其中 N 个矿石分别有其质量 W[i] 和价值 V[i]。检测标准是,将该矿石分成给定的 M 个区间(可能重叠或重复),每个区间的检验值等于该区间内所有质量不小于 W 的矿石的数量,乘以它们的价值之和。也就是 sigma(i,1)*sigma(i,V[i]) (L[i]<=i<=R[i] 且 Wi>=W) 。然后总的质量标准值 Y 为所有区间检验值的总和。其中, W 是某个质量标准参数。
该人员决定调整参数 W 的值,使得 Y 尽量接近规定的标准 S. 求 Y-S 的绝对值的最小值。

输入

输入第一行是三个整数 N,M,S 。接下来 N 行每行为矿石 i 的质量 W[i] 和 V[i]。再接下来 M 行每行是两个整数 L[i] R[i] ,表示一个区间[ L[i] , R[i] ]。

输出

输出一个整数,表示 Y-S 的绝对值的最小值。

提示


数据范围:



10% 1<=m,n<=10 



30% 1<=m,n<=500



50% 1<=m,n<=5000



70% 1<=m,n<=10000



100% 1<=m,n<=200,000, 0<Wi,Vi<=106, 0<s<=1010,1<=Li<=Ri<=N



NOIP2011 DAY2 qc

来源

 

[提交][状态]