山雨木子 @ 2017-12-24 10:23:07
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
int sum1[200010],sum2[200010];
ll ans=0x7fffffff,s,n,m;
ll L,R;
int w[200010],v[200010],l[200010],r[200010];
ll labs(ll a )
{
return a<0?-a:a;
}
int judge(ll mid)
{
memset(sum1,0,sizeof(sum1));
memset(sum2,0,sizeof(sum2));
for(int i=1;i<=n;i++)
{
sum1[i]=sum1[i-1];//表示1->i中大于标准的数量。
sum2[i]=sum2[i-1];//表示1->i中大于标准的矿石的价值之和
if(w[i]>=mid)
{
sum1[i]++;
sum2[i]+=v[i];
}
}
long long y=0;
for(int i=1;i<=m;i++)
{
y+=(sum1[r[i]]-sum1[l[i]-1])*(sum2[r[i]]-sum2[l[i]-1]);
}
ans=min(ans,labs(y-s));
return y-s>0;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&s);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&w[i],&v[i]);
R= max(R,(ll)w[i]);
}
for(int i=1;i<=m;i++)
scanf("%d%d",&l[i],&r[i]);
R++;
while(L<=R)
{
ll mid=(L+R)/2;
if(judge(mid))
L=mid+1;
else
R=mid-1;
}
printf("%lld",ans);
return 0;
}