LittleOcean @ 2024-12-06 12:10:20
#include<iostream>
#include<algorithm>
using namespace std;
const int N=200010;
typedef long long LL;
int n,m,s,l=1e9,r=-1;
LL res=0x3f3f3f3f3f3f;
int w[N],v[N],ql[N],qr[N];
LL sumn[N],sumv[N];
LL check(int x){
for(int i=1;i<=n;i++){
if(w[i]>=x)sumn[i]=sumn[i-1]+1,sumv[i]=sumv[i-1]+v[i];
else sumn[i]=sumn[i-1],sumv[i]=sumv[i-1];
}
LL y=0;
for(int i=1;i<=m;i++)y+=(sumn[qr[i]]-sumn[ql[i]-1])*(sumv[qr[i]]-sumv[ql[i]-1]);
return y;
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=n;i++){
scanf("%d%d",&w[i],&v[i]);
l=min(l,w[i]);
r=max(r,w[i]);
}
for(int i=1;i<=m;i++)scanf("%d%d",&ql[i],&qr[i]);
l--,r++;
while(l+1!=r){
int mid=(l+r)/2;
if(check(mid)>=s)l=mid;
else r=mid;
}
cout<<min(abs(check(l)-s),abs(check(r)-s));
}