记录编号	462297	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	Furyton	是否通过	通过
代码语言	C++	运行时间	0.679 s
提交时间	2017-10-21 18:57:52	内存使用	9.47 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define File(x) "qc."#x
#define For(i,s,e) for(int i=(s); i<=(e); i++)
#define Rep(i,s,e) for(int i=(s); i>=(e); i--)
#define ab(x) ((x)<0?-(x):(x))
#define Max(x,y) (x)=((x)<(y)?(y):(x))
using namespace std;

const int N=200000+10;
typedef long long LL;

int n,m;
LL v[N],w[N],L[N],R[N],ans=1000000000000,l,r=1000000000000+1,mid,s;
LL cnt[N],sum[N];

template <class T>
void read(T &x)
{
	char ch; int s=1;
	while(ch=getchar(),ch>'9' || ch<'0') if(ch=='-') s=-1;
	x=ch-'0';
	while(ch=getchar(),ch>='0' && ch<='9') x=x*10+ch-'0';
	x*=s;
}

bool can(LL x)
{
//	memset(cnt,0,sizeof(cnt));
//	memset(sum,0,sizeof(sum));
	LL tmp=0;
	For(i,1,n)
	{
		if(w[i]>=x) cnt[i]=cnt[i-1]+1,sum[i]=sum[i-1]+v[i];
		else sum[i]=sum[i-1],cnt[i]=cnt[i-1];
	}
	For(i,1,m)
	{
		tmp+=(cnt[R[i]]-cnt[L[i]-1])*(sum[R[i]]-sum[L[i]-1]);
	}

	ans=min(ans,ab(tmp-s));

	if(tmp<s) return 1;
	else return 0;
}

int main()
{
	freopen(File(in),"r",stdin);
	freopen(File(out),"w",stdout);

	cin>>n>>m>>s;
	For(i,1,n) read(w[i]),read(v[i]);

	For(i,1,m) read(L[i]),read(R[i]);

	while(l<r)
	{
		mid=(l+r+1)/2;
		if(can(mid)) r=mid-1;
		else l=mid;
	}

	cout<<ans<<endl;

	return 0;
}