```
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#pragma GCC optimize(3)
using namespace std;
const int INF=2000000000;
long long n,m,s,w[20005],v[20005],cnt[20005],tmp=INF,ans=INF;
pair<long long,long long>lr[20005];
long long sum[20005],res=0;
long long read()
{
long long num=0;
char c;
c=getchar();
while(c<'0'||c>'9')
{
c=getchar();
}
while(c>='0'&&c<='9')
{
num=num*10+c-'0';
c=getchar();
}
return num;
}
int pd(long long mid)
{
memset(cnt,0,sizeof(cnt));
memset(sum,0,sizeof(sum));
res=0;
for(int i=1;i<=n;i++)
{
int oo=w[i]>=mid;
cnt[i]=cnt[i-1]+oo;
sum[i]=sum[i-1]+(long long)(oo*v[i]);
}
for(int i=1;i<=m;i++)
{
res+=(cnt[lr[i].second]-cnt[lr[i].first-1])*(sum[lr[i].second]-sum[lr[i].first-1]);
}
long long kkk=res-s;
long long now=abs(kkk);
if(ans>now)ans=now;
if(res>=s)
{
return 1;
}
return 0;
}
int main()
{
n=read(),m=read(),s=read();
for(int i=1;i<=n;i++)
{
w[i]=read(),v[i]=read();
}
long long l,r;
for(int i=1;i<=m;i++)
{
l=read(),r=read();
lr[i]=make_pair(l,r);
}
l=0,r=tmp;
while(l<=r)
{
long long mid=(l+r)/2;
if(pd(mid)!=0)
{
l=mid+1;
}
else
{
r=mid-1;
}
}
cout<<ans<<endl;
return 0;
}
```
by 倾城ファン恋 @ 2018-02-21 17:02:15
你的INF要取9223372036854775807
by 渺小的Mastar @ 2019-04-05 04:09:57