Problem1446--聪明的质监员

1446: 聪明的质监员

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description

有个质量监督员负责检查矿石质量。 其中 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 的绝对值的最小值。

Input

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

Output

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

HINT

数据范围:
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

Source/Category