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
// Aleksander Kramarz

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int n, m, num, pos[500001];
vector<int> cuts;
long long a[500001], sum[500001], d[500001], b[500001];

int find_pos(int p, int q) {
	long long h = cuts.empty() ? 0 : b[cuts.back()];
	long long t = d[num] - (cuts.empty() ? 0 : d[cuts.back()]);
	while (p < q) {
		int x = (p+q) / 2;
		if (a[x] * t + h < b[num])
			p = x+1;
		else
			q = x;
	}
	return p;
}

long long cut() {
	long long res = 0;
	int end = n;
  while (!cuts.empty() && b[num] <= b[cuts.back()] + (d[num] - d[cuts.back()]) * a[pos[cuts.back()]]) {
    int j = cuts.back();
    res += (sum[pos[j]] - sum[end]) * (d[num] - d[j]) - (b[num] - b[j]) * (end - pos[j]);
    end = pos[j];
    cuts.pop_back();
  }
	int ind = cuts.empty() ? 500000 : cuts.back();
	int beg = pos[ind];
	int new_cut = find_pos(beg, end);
	pos[num] = new_cut;
	res += (sum[new_cut] - sum[end]) * (d[num] - d[ind]) - (b[num] - b[ind]) * (end - new_cut) ;
	if (new_cut < n)
    cuts.push_back(num);
	return res;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%lld", a+i);
	sort(a, a+n);
	for (int i = n-1; i >= 0; i--)
		sum[i] = sum[i+1] + a[i];
	for (num = 0; num < m; num++) {
		scanf("%lld%lld", d+num, b+num);
		printf("%lld\n", cut());
	}
}