1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
#define ll long long

struct kosz{
	ll d,b,ile,a;
	kosz(ll d,ll b,ll ile, ll a) :d(d),b(b),ile(ile),a(a) {}
};
stack<kosz> S;

int a[500001],e[1000002];
ll  s[500001];

int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for (int i=n;i>0;i--) {s[i]=s[i+1]+a[i]; e[a[i]]=i;}
	for (int i=1000000;i>0;i--) 		if (e[i]==0) e[i]=e[i+1];
	//for (int i=1;i<=n;i++) printf("%d(%lld) ",a[i],s[i]);puts("");
	//for (int i=1;i<=10;i++) printf("%d[%d] ",i,e[i]);puts("");
	S.push(kosz(0,0,0,0));
	while (m--) {
		ll d,b;
		scanf("%lld%lld",&d,&b); //printf("d=%lld b=%lld\n",d,b);
		if (a[n]<=(b-S.top().b)/(d-S.top().d)) {printf("0\n");continue;}
		ll sum=0;
		while (S.top().a>(b-S.top().b)/(d-S.top().d)) {
			sum += S.top().ile; //printf("zd %d\n",S.top().d);
			S.pop();
		}
		int r = (b-S.top().b)/(d-S.top().d)+1;
		int e1 = e[r];
		ll ile = s[e1]*(d-S.top().d)-(b-S.top().b)*(n-e1+1); //printf("ile=%lld r=%d\n",ile,r);
		printf("%lld\n",ile-sum);
		S.push(kosz(d,b,ile,r));
	}
	return 0;
}