记录编号	277969	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	631.[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	iortheir	是否通过	通过
代码语言	C++	运行时间	1.374 s
提交时间	2016-07-06 20:52:19	内存使用	9.00 MiB

//杨俊论文
#include<iostream>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
LL n,m,s;
LL w[200010];
LL v[200010];
LL l[200010];
LL r[200010];
LL V[200010];
LL V1[200010];//存下标
LL maxn=0;
LL ans=0;
inline long long ysum(int W)//求Y
{
	V[0]=0;
	V1[0]=0;
	for(int i=1;i<=n;++i)
	{
		if(w[i]>W)//**********************************W随机
		{
			V[i]=V[i-1]+v[i];
			V1[i]=V1[i-1]+1;
		}
		else 
		{
			V[i]=V[i-1];
			V1[i]=V1[i-1];
		}
	}
	LL sum=0;
	for(int i=1;i<=m;++i)
	{
		sum+=(V1[r[i]]-V1[l[i]-1])*(V[r[i]]-V[l[i]-1]);
	}
	return sum;
}
inline void erfen()
{
	LL Y;
	int left=0;
	int right=maxn;
	int mid;
	while(left<=right)
	{
		mid=(left+right)/2;
		Y=ysum(mid);
		if(Y<s)
		{
			right=mid-1;
		}
		else 
			left=mid+1;
	}
	LL x,y;//检验是否接近QAQ
	x=abs(ysum(left)-s);
	y=abs(ysum(right)-s);
	if(x<y)
	{
		ans=x;
	}
	else
	{
		ans=y;
	}
}
int main()
{
	freopen("qc.in","r",stdin);
	freopen("qc.out","w",stdout);
	cin>>n>>m>>s;
	for(int i=1;i<=n;++i)
	{
		cin>>w[i]>>v[i];
		if(w[i]>maxn)
		{
			maxn=w[i];
		}
	}
	for(int i=1;i<=m;++i)
	{
		cin>>l[i]>>r[i];
	}
	erfen();
	cout<<ans<<endl;
	return 0;
}
/*
																				qc.in
																				5 3 15 矿石的个数、区间的个数和标准值
																				1 5
                                                                                2 5
                                                                                3 5
																				4 5
                                                                                5 5
***********************************************************************************
                                                                                1 5
                                                                                2 4
                                                                                3 3
                                                                                qc.out
																				10
*/