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
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef long long ll;
const int nax = 5e5 + 5;

int n, speed[nax];

/*namespace Brut {
	ll was[nax];
	ll prevTime;
	ll f(ll t, ll c) {
		for(int i = 1; i <= n; ++i) {
			was[i] += (t - prevTime) * a[i];
			assert(was[i] <= 1e13L);
		}
		ll s = 0;
		for(int i = 1; i <= n; ++i) if(was[i] > c) {
			s += was[i] - c;
			was[i] = c;
		}
		prevTime = t;
		return s;
	}
}*/

ll pref[nax];
ll sumSpeed(int i, int j) {
	return pref[j] - (i ? pref[i-1] : 0);
}
ll levelTo(int i, int j, ll dt, ll db) {
	return dt * sumSpeed(i, j) - db * (j - i + 1);
}

struct Cut {
	ll t, b;
	Cut(ll tt, ll bb) : t(tt), b(bb) {}
	ll val(int i, ll tm) { return speed[i] * (tm - t) + b; }
};

vector<pair<int,Cut> > w = vector<pair<int,Cut> >{make_pair(0, Cut(0,0))};

ll f(ll t, ll b) {
	if(b >= w.back().nd.val(n, t))
		return 0;
	int till = n;
	ll s = 0;
	while(true) {
		pair<int,Cut> & A = w.back();
		ll pre = A.nd.val(A.st, t);
		if(b <= pre) {
			// completely remove w.back()
			s += levelTo(A.st, till, t - A.nd.t, b - A.nd.b);
			till = A.st - 1;
			w.pop_back();
		}
		else {
			int low = A.st, high = till;
			// where is the last unchanged
			while(low < high) {
				int m = (low + high + 1) / 2;
				if(b > A.nd.val(m, t)) low = m;
				else high = m - 1;
			}
			s += levelTo(low + 1, till, t - A.nd.t, b - A.nd.b);
			w.push_back(make_pair(low + 1, Cut(t, b)));
			return s;
		}
	}
}

int main() {
	int q;
	scanf("%d%d", &n, &q);
	speed[0] = -1;
	for(int i = 1; i <= n; ++i)
		scanf("%d", &speed[i]);
	sort(speed + 1, speed + n + 1);
	for(int i = 1; i <= n; ++i)
		pref[i] = speed[i] + pref[i-1];
	while(q--) {
		ll t, b;
		scanf("%lld%lld", &t, &b);
		printf("%lld\n", f(t, b));
	}
	return 0;
}