有个质量监督员负责检查矿石质量。 其中 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<=10⁶, 0<s<=10¹⁰,1<=Li<=Ri<=N

NOIP2011 DAY2 qc