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
134
135
136
137
138
139
140
141
#include <iostream>
#include <cstdio>
#include <ctime>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 500007;
int n, m;
const int M = 1 << 19;
int a[M << 1];
long long sum[M << 1];
long long W[M << 1];
long long w[M << 1];
long long tt[M << 1];
bool akt[M << 1];
long long HH[N];
long long TT[N];
int idd = 1;
int D[M << 1];

inline void insert2(int x, int w) {
	x += M;
	while(x > 0) {
		D[x] = max(D[x], w);
		x >>= 1;
	}
}

inline long long insert(int a, int b, long long H, long long T, int v = 1, int p = 0, int k = M - 1) {
	int len = k - p + 1;

	if(a <= p && k <= b) {
		if(akt[v]) W[v] = w[v] * len;
		long long ret = W[v] + sum[v] * (T - tt[v]);
		w[v] = H;
		tt[v] = T;
		akt[v] = 1;
		W[v] = w[v] * len;
		return ret;
	}

	if(akt[v]) {
		W[v] = w[v] * len;
		w[(v << 1)] = w[v];
		w[(v << 1) + 1] = w[v];
		W[(v << 1)] = W[v] >> 1;
		W[(v << 1) + 1] = W[v] >> 1;
		tt[(v << 1)] = tt[v];
		tt[(v << 1) + 1] = tt[v];
		akt[(v << 1)] = 1;
		akt[(v << 1) + 1] = 1;
		akt[v] = 0;
	}
	int s = (p + k) / 2;
	long long res = 0;
	W[v] = 0;
	if(s >= a) res += insert(a, b, H, T, (v << 1), p, s);
	else W[v] += sum[(v << 1)] * (T - tt[(v << 1)]);
	if(s < b) res += insert(a, b, H, T, (v << 1) + 1, s + 1, k);
	else W[v] += sum[(v << 1) + 1] * (T - tt[(v << 1) + 1]);
	W[v] += W[(v << 1)] + W[(v << 1) + 1];
	tt[v] = T;
	return res;
}

inline int znajdz(long long H, long long T) {
	int v = 1;
	int res = 0;
	int k = M - 1;
	int p = 0;
	while(v < M) {
		int res2 = max(res, D[v << 1]);
		int s = (p + k) / 2;
		if(HH[res2] + (T - TT[res2]) * a[min(s, n)] <= H) {
			res = res2;
			v = (v << 1) + 1;
			p = s + 1;
		}
		else {
			v <<= 1;
			k = s;
		}
	}
	return v - M;
}

inline long long readLL() {
	long long res = 0;
	char zn = getchar();
	while(isspace(zn)) zn = getchar();
	do {
		res = (res << 3) + (res << 1) + zn - '0';
		zn = getchar();
	} while(!isspace(zn));
	return res;
}

inline int readINT() {
	int res = 0;
	char zn = getchar();
	while(isspace(zn)) zn = getchar();
	do {
		res = (res << 3) + (res << 1) + zn - '0';
		zn = getchar();
	} while(!isspace(zn));
	return res;
}

int main() {
	n = readINT();
	m = readINT();
	for(int i = 1; i <= n; ++i) {
		a[i] = readINT();
	}
	sort(a + 1, a + 1 + n);
	for(int i = 1; i <= n; ++i) {
		sum[M + i] = a[i];
	}
	for(int i = M - 1; i > 0; --i) {
		sum[i] = sum[i << 1] + sum[(i << 1) + 1];
	}

	for(int it = 0; it < m; ++it) {
		long long d, b;
		d = readLL();
		b = readLL();
		int gd = znajdz(b, d);
		long long res = 0;
		if(gd <= n) {
			res += insert(gd, n, b, d);
			res -= b * (n - gd + 1);
			HH[idd] = b;
			TT[idd] = d;
			insert2(gd, idd++);
		}
		printf("%lld\n", res);
	}
	//system("pause");
	return 0;
}