记录编号	324674	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	农场主	是否通过	通过
代码语言	C++	运行时间	1.030 s
提交时间	2016-10-18 16:58:45	内存使用	76.58 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 2000001 
using namespace std;
typedef long long ll;
class poi{
public:
	int l,r;
};
poi q[maxn];
ll w[maxn];
ll v[maxn];
ll pre[maxn]={0};
ll cnt[maxn]={0};
ll n,m,s;
void read(){
	scanf("%lld%lld%lld",&n,&m,&s);
	for (int i=1;i<=n;i++){
		scanf("%lld%lld",&w[i],&v[i]);
	}
	for (int i=1;i<=m;i++){
		scanf("%d%d",&q[i].l,&q[i].r);
	}
}
ll check(ll x){
	cnt[0]=0;
	pre[0]=0;
	for (int i=1;i<=n;i++){
		pre[i]=pre[i-1];
		cnt[i]=cnt[i-1];
		if (w[i]>=x){
			pre[i]+=v[i];
			cnt[i]++;
		}
	}
	ll y=0;
	for (int i=1;i<=m;i++){
		y+=(ll)(cnt[q[i].r]-cnt[q[i].l-1])*(pre[q[i].r]-pre[q[i].l-1]);
	}
	return y;
}
ll lower_bound(ll s){
	ll l=1,r=100000000,mid,ans=ll(1)<<60;
	while(l<r){
		mid=(l+r>>1);
		if (check(mid)>s){
			l=mid+1;
		}
		else{
			r=mid;
		}
	}
	ans=abs(check(l)-s);
	l=1,r=100000000;
	while(l+1<r){
		mid=(l+r)>>1;
		if (check(mid)<s){
			r=mid-1;
		}
		else l=mid;
//		printf("%d %d %d\n",l,r,check(mid)-s);
	}
	ans=min( ans , abs ( check(r) - s ) );
	ans=min( ans , abs ( check(l) - s ) );
	return ans;
}
int main(){
	freopen("qc.in","r",stdin);
	freopen("qc.out","w",stdout);
	read();
	ll ans=lower_bound(s);
	printf("%lld",ans);
}