记录编号	472059	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	snake	是否通过	通过
代码语言	C++	运行时间	0.479 s
提交时间	2017-11-07 10:14:06	内存使用	7.94 MiB

//#include<iostream>
#include<cstring>
#include<fstream>
#include<algorithm>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<climits>
using namespace std;
ifstream cin("qc.in");ofstream cout("qc.out");

const int MAX=200010;
long long v[MAX],w[MAX];
long long sumv[MAX];	//sumv[i] 前i个中满足w>=W的物品价值和 
long long sumn[MAX];	//sumv[i] 前i个中满足w>=W的物品计数 
int area[2][MAX];	//第i个区间left=area[0][i],right=area[1][i] 
int n,m;
long long s;

long long deal(int W)
{
	
	for(int i=1;i<=n;i++)
	{
		if(w[i]>W) {sumn[i]=sumn[i-1]+1;sumv[i]=sumv[i-1]+v[i];}
		else {sumn[i]=sumn[i-1];sumv[i]=sumv[i-1];}
	}
	
	long long t=0;
	for(int i=1;i<=m;i++) t+=(sumn[area[1][i]]-sumn[area[0][i]-1])*(sumv[area[1][i]]-sumv[area[0][i]-1]);
	
	return t;
}

int main()
{
	ios::sync_with_stdio(false);
	
	cin>>n>>m>>s;
	int maxw=INT_MIN,minw=INT_MAX;
	
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
		if(w[i]>maxw) maxw=w[i];
		if(w[i]<minw) minw=w[i];
	}
	
	for(int i=1;i<=m;i++) cin>>area[0][i]>>area[1][i];
	
	int left=minw,right=maxw;
	int mid=(left+right)/2;
	long long t,dis=LLONG_MAX;
	
	while(left<right)
	{
		t=deal(mid);
		if(t>s)
		{
			left=mid+1;
			if(t-s<dis) dis=t-s;
		}else if(t<s){
			right=mid;
			if(s-t<dis) dis=s-t;
		}else{
			dis=0;
			break;
		}
		mid=(left+right)/2;
	}
	
	cout<<dis;
	return 0;
}