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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <stdlib.h>

#define find_first(n, first, cond) \
{ \
  long long i, _s, _c = n; \
  first = 0; \
  while (_c>0) { \
    _s=_c/2; i = first + _s; \
    if (cond) _c=_s; else { \
      first=++i; \
      _c-=_s+1; \
    } \
  } \
}



int n,m;
int v[500100];
int st[500100];
int sn[500100];
int sp[500100];
int ss;
long long sums[500100];
int cmp(int *a, int *b) { return *a>*b?-1:*a<*b; }
int main() {
	int i;
	scanf("%d%d",&n,&m);
	for (i = 0; i < n; i++) {
		scanf("%d",v+i);
	}
	sp[0] = n;
	qsort(v, n, sizeof(*v), cmp);
	for (i = 0; i < n; i++) {
		sums[i+1] = sums[i] + v[i];
//		printf("%d %lld\n",v[i],sums[i+1]);
	}
	for (i = 0; i < m; i++) {
		long long t = 0;
		int nn,t1,b,pos,start = 0,s2;
		scanf("%d%d",&t1,&b);
		do {
			int tx = st[ss];
			int lx = sn[ss];
			nn = sp[ss] - start;
//			printf("len=%d %d\n",sp[ss],start);
			s2 = start;
			find_first(nn, pos, v[start+i] * (long long)(t1-tx) + lx <= b);
			t += (long long)(lx-b) * pos + (sums[start+pos]-sums[start]) * (t1-tx);
//			printf("%d %lld %d\n",(lx-b)*pos, sums[start+pos]-sums[start], t1-tx);
//			printf("lx%d nn%d ss%d %d %d %lld %d\n",lx,nn,ss,t1-tx,b,t,pos);
			if (pos == nn) {
				ss--;
				start += nn;
			}
		} while (pos == nn && ss >= 0);
		printf("%lld\n", t);
		if (start + pos) {
			st[++ss] = t1;
			sn[ss] = b;
			sp[ss] = s2 + pos;
//			if (s2 + pos > n) printf ("BAD! %d %d %d\n",s2,nn,pos);
		}
//		for (s2 = 0; s2 <= ss; s2++) printf("%d(%d) ",sp[s2],st[s2]); puts(" STACK");
	}
	return 0;
}