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
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <cassert>
#include <cstdio>
#include <algorithm>
#define MAXN 500007
#define MAXM 500007
using namespace std;

//#define DEBUG

#ifdef DEBUG
#define ASSERT(x) assert(x)
#else
#define ASSERT(X)
#endif

typedef long long slng;

int N, M;
int a[MAXN];
slng suma[MAXN+1];
// [i] = on day d[i] cut to b[i] starting from a[ind[i]].
// d[i] ascending, b[i] ascending, ind[i] ascending.
slng numd, d[MAXM], b[MAXM], ind[MAXM];

// find lowest affected d.
int findd(slng di, slng bi) {
	int l = 0, r = numd;
	while (l != r) {
		int s = (l+r)/2;
		slng ah = (s != numd-1) ? a[ind[s+1] - 1] : a[N-1];
		if (b[s] + (di - d[s]) * ah <= bi /* not affected by cutting at bi */) {
			l = s+1;
		} else /* affected by cutting at bi. */ {
			r = s;
		}
	}
	return l;
}

// find lowest affected a.
int finda(int dd, slng di, slng bi) {
	int l, r, initr;
	l = ind[dd];
	initr = r = (dd < numd-1) ? ind[dd+1] : N;
	while (l != r) {
		int s = (l+r)/2;
		if (b[dd] + (di - d[dd]) * (slng) a[s] <= bi /* not affected by cutting at bi */) {
			l = s+1;
		} else /* affected by cutting at bi. */ {
			r = s;
		}
	}
	ASSERT(l != initr);
	ASSERT(b[dd] + (di - d[dd]) * (slng) a[l] >= bi);
	return l;
}

slng cut(int dd, int aa, slng di, slng bi) {
	slng ret = 0;
	int i;
	int ar;
	
	ar = (dd < numd-1) ? ind[dd+1] : N;
	ret += (b[dd] - bi /* <= 0 here*/) * (slng)(ar - aa);
	ret += (di - d[dd]) * (suma[ar] - suma[aa]);
#ifdef DEBUG
	printf("ret=%lld", ret);
#endif
	for (i = dd+1; i < numd; i++) {
		ar = (i < numd-1) ? ind[i+1] : N;
		ret += (b[i] - bi) * (slng)(ar - ind[i]);
		ret += (di - d[i]) * (suma[ar] - suma[ind[i]]);
#ifdef DEBUG
		printf(" %lld", ret);
#endif
	}
#ifdef DEBUG
	printf("\n");
#endif
	return ret;
}


int main() {
	int i;
#ifdef DEBUG
	int j;
#endif
	
	scanf("%d%d", &N, &M);
	for (i = 0; i < N; i++)
		scanf("%d", &a[i]);
	// sort and partial sums.
	sort(a, a+N);
	// suma[N] = sum(a,[0,N-1])
	suma[0] = 0;
	for (i = 1; i <= N; i++)
		suma[i] = suma[i-1] + a[i-1];

	// everything cut at 0 on the 0th day.
	numd = 1;
	d[0] = 0; b[0] = 0; ind[0] = 0;
	for (i = 0; i < M; i++) {
		slng di, bi;
		int dd, aa;
		
		scanf("%lld%lld", &di, &bi);
#ifdef DEBUG
		printf("di=%lld bi=%lld\n", di, bi);
		for (j = 0; j < numd; j++) {
			printf("(d=%lld b=%lld a[ind=%lld]=%d) ", d[j], b[j], ind[j], a[ind[j]]);
		}
		printf("\n");
#endif
		dd = findd(di, bi);
		if (dd == numd) {
			printf("0\n");
			continue;
		}
		aa = finda(dd, di, bi);
		ASSERT(bi > b[dd] || aa == ind[dd]);
#ifdef DEBUG
		printf("dd=%d aa=%d\n", dd, aa);
#endif
		printf("%lld\n", cut(dd, aa, di, bi));
		if (aa == ind[dd])
			dd--; // overwrite
		d[dd+1] = di; b[dd+1] = bi; ind[dd+1] = aa;
		numd = dd+2;
	}
	
	return 0;
}