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
#include <iostream>
#include <algorithm>
using namespace std;

long long a[500010];
long long b[500010][3];
long long sum[500010];

int znajdz(int p, int k, long long wys, long long dni) {
	while(p != k) {
		int s = (p + k) / 2;
		if(wys + dni * a[s] >= 0) {
			k = s;
		}
		else {
			p = s + 1;
		}
	}
	return p;
}

int main() {
	ios_base::sync_with_stdio(0);
	long long n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= n; i ++) {
		sum[i] = sum[i - 1] + a[i];
	}
	long long wys, dzien, wyn;
	int x = 0, kon;
	b[x][0] = 1;
	for(int i = 0; i < m; i ++) {
		cin >> dzien >> wys;
		kon = n + 1;
		wyn = 0;
		while(x >=0 && b[x][2] + (dzien - b[x][1]) * a[b[x][0]] >= wys) {
				wyn += (b[x][2] - wys) * (kon - b[x][0]) + (dzien - b[x][1]) * (sum[kon - 1] - sum[b[x][0] - 1]);
				kon = b[x][0];
				x --;
		}
		int poz = 1;
		if(x >= 0) {
			poz = znajdz(b[x][0], kon, b[x][2] - wys, dzien - b[x][1]);
			wyn += (b[x][2] - wys) * (kon - poz) + (dzien - b[x][1]) * (sum[kon - 1] - sum[poz - 1]);
		}
		if(poz <= n) {
			x ++;
			b[x][0] = poz;
			b[x][1] = dzien;
			b[x][2] = wys;
		}
		cout << wyn << endl;
	}
}