首先有一个最简单的想法：枚举所有的 W。

那么此时 y 可以简单地求出：只需把所有重量小于 W 的矿石看成不存在（即不算数，也不算价值），对权值和数量各自做前缀和，然后直接按照式子把所有区间的贡献加起来就行了。复杂度 O(wi​(n+m))，显然过不了。

进一步优化可以改成只枚举 W=wi​ 的这部分 W，因为取两个 wi​ 中间的空当和直接取较大的那个 wi​ 没有什么区别，不会影响重量 ≥W 的矿石的集合。这样做复杂度是 O(n(n+m)) 的，还是过不了。可能在现在的评测机上可以获得 70 分。

考虑题目的问题：出题人希望我们找到一个尽可能逼近 s 的结果。类似在一个范围内猜确定的数字，我们很容易发现这个题的 W 产生的性质和猜数字没什么区别。因为所有权值都是正的，所以 W 越大，反倒 y 越小，这样的单调性完全支持我们通过二分的方式逼近到 s 附近。

具体来说，我们二分一个 W，如果这个 W 产生的 y 比 s 大，则说明 W 更大可能可以更接近，更小则一定不如这个值；反之亦然。

于是我们总可以二分到一个 s 附近的值：这个值满足要么是 y=s 的 W，要么就是比 y<s 的最小 W，要么就是 y>s 的最大 W。

所以我们再检验我们二分出来的 W 和它的周围两个（W−1,W+1），在这至多三个 W 中取 min 就可以了。事实上一边二分一边取 min 也是可以的。

时间复杂度 O(mlogwi​)。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll sumw[200010],sumv[200010];
int n,m,w[200010],v[200010],r[200010],l[200010];
int minn=INT_MAX,maxn=-20040615;
ll ans=1e18,s,sum,x;
bool check(int wans){
	x=sum=0;
	memset(sumw,0,sizeof(sumw));
	memset(sumv,0,sizeof(sumv));
	for(int i=1;i<=n;i++){
		if(w[i]>=wans){
			sumw[i]=sumw[i-1]+1;
			sumv[i]=sumv[i-1]+v[i];
		}
		else{
			sumw[i]=sumw[i-1];
			sumv[i]=sumv[i-1];
		}
	}
	for(int i=1;i<=m;i++){
		x+=(sumw[r[i]]-sumw[l[i]-1])*(sumv[r[i]]-sumv[l[i]-1]);
	}
	sum=llabs(x-s);
	if(x>s){
		return true;
	}
	else{
		return false;
	}
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
		minn=min(minn,w[i]);
		maxn=max(maxn,w[i]);
	}
	for(int i=1;i<=m;i++){
		cin>>l[i]>>r[i];
	}
	int l1=minn-1,r1=maxn+2;
	while(l1!=r1){
		int mid=(l1+r1)/2;
		if(check(mid)){
			l1=mid+1;
		}
		else{
			r1=mid;
		}
		ans=min(sum,ans);
	}
	cout<<ans<<endl;
	return 0;
}