一念之间 @ 2017-03-26 20:09:25
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mid,start,end,ans,n,m,s,w[10000],v[10000],l[10000],r[10000],sum[10000],sumv[10000];
void work(ll s)
{sum[0]=0ll;
sumv[0]=0ll;
for(int i=1;i<=n;i++)
if(w[i]>=s)
{
sum[i]=sum[i-1]+1;
sumv[i]=sumv[i-1]+v[i];
}
else
{sum[i]=sum[i-1];
sumv[i]=sumv[i-1];
}
}
ll qxh(ll mid)
{
ll ss=0;
for(int i=1;i<=m;i++)
ss=(sum[r[i]]-sum[l[i]-1])*(sumv[r[i]]-sumv[l[i]-1]);
return ss;
}
ll bijiao(ll a)
{
if(a>0) return a;
else return -a;
}
int main()
{
ans=99999999999;
start=0ll;end=0ll;
cin>>n>>m>>s;
for(int i=1;i<=n;i++)
{cin>>w[i]>>v[i];
if(w[i]>end) end=w[i];
}
for(int i=1;i<=m;i++)
cin>>l[i]>>r[i];
while(start<=end)
{
mid=(start+end)/2;
work(mid);
ll t=qxh(mid);
if(bijiao(t-s)<ans)
ans=bijiao(t-s);
if(ans==0) break;
if(s<t) start=mid+1;
else end=mid-1;
}
cout<<ans<<endl;
return 0;
}