记录编号	395985	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	0.477 s
提交时间	2017-04-17 19:12:49	内存使用	9.47 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long lg;
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)
#define MAXX 200011
//#define OPEN 

lg n,m,k,s,w[MAXX],v[MAXX],l[MAXX],r[MAXX];
lg maxn=0,minn=1e16,mii=1e10;
lg sum[MAXX],num[MAXX];

lg read()
{
	lg res=0;
	char c;
    while((c=getchar())>='0' && c<='9')
      res=res*10+c-'0';
	return res;
}

void out(lg n)
{
	if(n>9) out(n/10);
	putchar(n%10+'0');
}


bool pd(int n)
{
	memset(sum,0,sizeof sum);
	memset(num,0,sizeof num);
	lg su=0;
	for(int i=1;i<=::n;i++)
	{
		//if(w[i]<n)
		sum[i]=sum[i-1];
		num[i]=num[i-1];
		if(w[i]>=n)
		{
			sum[i]+=v[i];
         	num[i]++;
		}
	}

	for(int i=1;i<=m;i++)
	  su+=(sum[r[i]]-sum[l[i]-1])*(num[r[i]]-num[l[i]-1]);
    minn=min(minn,abs(su-s));
    if(su==s)
	{
      out(0);	
      exit(EXIT_SUCCESS);
	}
    return su-s>=0;
}

inline void f(int l,int r)
{
	if(r-l<=1)
	{
		pd(l);
		pd(r);
		return;
	}
	int m=(l+r)>>1;
	if(!pd(m)) 
		f(l,m);
	else 
       f(m,r);
}

int main(int argc, char** argv)
{
	freopen("qc.in","r",stdin),freopen("qc.out","w",stdout);
    n=read();
    m=read();
    s=read();
    for(int i=1;i<=n;i++)
	{
		w[i]=read();
		v[i]=read();
	    maxn=max(maxn,w[i]);	
	    mii=min(mii,w[i]);
	}
    for(int i=1;i<=m;i++)
    {
		l[i]=read();
		r[i]=read();
	}
    f(mii,maxn);
    out(minn);
	return 0;
}