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
#include <cstdio>
#include <algorithm>
#include <map>

const int N = 500010;

typedef long long LL;

struct Interval {
	int begin;
	int end;
	LL day;
	LL height;

	Interval() = default;

	Interval(int b, int e, LL d, LL h) :
		begin(b), end(e), day(d), height(h) {}
};

int speed[N];
LL sum[N];

LL calc_height(int speed, LL current_day, LL cut_day, LL cut_height) {
	return cut_height + (current_day - cut_day) * (LL)(speed);
}

LL calc_begin_height(const Interval &i, LL current_day) {
	return calc_height(speed[i.begin], current_day, i.day, i.height);
}

LL calc_end_height(const Interval &i, LL current_day) {
	return calc_height(speed[i.end - 1], current_day, i.day, i.height);
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i) {
		scanf("%d", speed + i);
	}
	std::sort(speed, speed + n);
	sum[0] = speed[0];
	for (int i = 1; i < n; ++i) {
		sum[i] = sum[i - 1] + (LL)speed[i];
	}

	std::map<int, Interval> intervals;
	intervals[0] = Interval(0, n, 0, 0);

	for (int i = 0; i < m; ++i) {
		LL d, h;
		scanf("%lld%lld", &d, &h);
		
		int p = 0;
		int k = n - 1;
		while (p < k) {
			int mid = (p + k) / 2;
			auto it = intervals.upper_bound(mid);
			--it;
			LL h2 = calc_height(speed[mid], d, it->second.day, it->second.height);
			//printf("BS: m=%d h=%lld, i=(%d %d %lld %lld)\n", mid, h2,
			//		it->second.begin, it->second.end, it->second.day, it->second.height);
			if (h2 < h) {
				p = mid + 1;
			} else {
				k = mid;
			}
		}
		if (p == n) {
			printf("0\n");
			continue;
		}
		auto it = intervals.upper_bound(p);
		--it;
		auto prev = it->second;
		LL res = (sum[it->second.end - 1] - (p > 0 ? sum[p - 1] : 0)) * (d - it->second.day)
			+ (LL)(it->second.end - p) * it->second.height;
		//printf("Res = %lld begin = %d\n", res, it->second.begin);
		it = intervals.erase(it);

		while (it != intervals.end()) {
			res += (sum[it->second.end - 1] - sum[it->second.begin - 1]) * (d - it->second.day)
				+ (LL)(it->second.end - it->second.begin) * it->second.height;
			//printf("Res = %lld begin = %d\n", res, it->second.begin);
			it = intervals.erase(it);
		}
		if (p != prev.begin) {
			intervals.insert(std::make_pair(prev.begin, Interval(prev.begin, p, prev.day, prev.height)));
		}
		intervals.insert(std::make_pair(p, Interval(p, n, d, h)));

		res -= (LL)(n - p) * h;
		printf("%lld\n", res);
	}

	return 0;
}