luoguT21777

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, m;
ll a[500005], uu, vv, lst, qzh[500005];
struct SGT{
	ll sum[2000005], tag[2000005], fla[2000005], zdz[2000005];
	void update(int o, int l, int r, ll k){
		sum[o] += (qzh[r]-qzh[l-1]) * k;
		tag[o] += k;
		zdz[o] += a[r] * k;
	}
	void reset(int o, int l, int r, ll k){
		sum[o] = (r-l+1) * k;
		zdz[o] = fla[o] = k;
		tag[o] = 0;
	}
	void pushDown(int o, int l, int r, int lson, int rson, int mid){
		if(fla[o]!=-1){
			reset(lson, l, mid, fla[o]);
			reset(rson, mid+1, r, fla[o]);
			fla[o] = -1;
		}
		if(tag[o]){
			update(lson, l, mid, tag[o]);
			update(rson, mid+1, r, tag[o]);
			tag[o] = 0;
		}
	}
	int queryPos(int o, int l, int r, ll k){
		if(l==r)	return l;
		else{
			int mid=(l+r)>>1;
			int lson=o<<1;
			int rson=lson|1;
			pushDown(o, l, r, lson, rson, mid);
			if(zdz[lson]>=k)	return queryPos(lson, l, mid, k);
			else	return queryPos(rson, mid+1, r, k);
		}
	}
	ll querySum(int o, int l, int r, int x, int y){
		if(l>=x && r<=y)	return sum[o];
		else{
			int mid=(l+r)>>1;
			int lson=o<<1;
			int rson=lson|1;
			ll ans=0;
			pushDown(o, l, r, lson, rson, mid);
			if(x<=mid)	ans += querySum(lson, l, mid, x, y);
			if(mid<y)	ans += querySum(rson, mid+1, r, x, y);
			return ans;
		}
	}
	void modify(int o, int l, int r, int x, int y, ll k){
		if(l>=x && r<=y)	reset(o, l, r, k);
		else{
			int mid=(l+r)>>1;
			int lson=o<<1;
			int rson=lson|1;
			pushDown(o, l, r, lson, rson, mid);
			if(x<=mid)	modify(lson, l, mid, x, y, k);
			if(mid<y)	modify(rson, mid+1, r, x, y, k);
			sum[o] = sum[lson] + sum[rson];
			zdz[o] = zdz[rson];
		}
	}
}sgt;
int main(){
	cin>>n>>m;
	for(int i=1; i<=n; i++)	scanf("%lld", &a[i]);
	sort(a+1, a+1+n);
	for(int i=1; i<=n; i++)	qzh[i] = qzh[i-1] + a[i];
	memset(sgt.fla, -1, sizeof(sgt.fla));
	while(m--){
		scanf("%lld %lld", &uu, &vv);
		sgt.update(1, 1, n, uu-lst);
		lst = uu;
		if(sgt.zdz[1]<vv){
			printf("0
");
			continue;
		}
		int pos=sgt.queryPos(1, 1, n, vv);
		printf("%lld
", sgt.querySum(1, 1, n, pos, n)-(n-pos+1)*vv);
		sgt.modify(1, 1, n, pos, n, vv);
	}
	return 0; 
}