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
#define NDEBUG
#include <cstdio>
#include <cctype>
#include <cassert>
#include <functional>
#include <algorithm>
#include <map>
#include <utility>
#include <iostream>
using namespace std;

char ch;

template<class T>
inline void read(T &x) {
	while(!isdigit(ch = getchar_unlocked()));
	x = ch-'0';	
	while( isdigit(ch = getchar_unlocked())) x *= 10, x += ch-'0'; 
}

const int MAXN = 500001;
int a[MAXN + 1], n;
long long prefix_sum[MAXN + 1];
map<int, pair<long long, long long>> tree;

void init() {
	for(int i = 0; i < n; ++i) read<int>(a[i]);
	sort(a, a + n, greater<int>());	
	a[n] = 0;

	prefix_sum[0] = 0; 
	for(int i = 0; i < n; ++i) prefix_sum[i + 1] = prefix_sum[i] + a[i];
	
	tree.emplace(n, make_pair(0, 0));
}

inline long long get_height(int idx, long long day) {
	pair<long long, long long> t = tree.lower_bound(idx)->second;
	return t.second + (day - t.first) * a[idx];
}

inline int find_cut_index(long long day, long long level) {
	int lo = 0, hi = n - 1, mid;
	while(lo < hi) {
		mid = lo + (hi - lo + 1) / 2;
		if(get_height(mid, day) >= level) lo = mid; else hi = mid - 1;
	}
	return lo;
}

long long calc_cutoff(int cut_index, long long day, long long level) {
	int prev_cut = -1;
	long long res = -(cut_index + 1) * level;
	for(auto it = tree.begin(); it != tree.end();) {
		if(it->first < cut_index) {
			assert(numeric_limits<long long>::max() / (day - it->second.first) >= (prefix_sum[it->first + 1] - prefix_sum[prev_cut + 1])); 
			res += (day - it->second.first) * (prefix_sum[it->first + 1] - prefix_sum[prev_cut + 1]) + (it->first - prev_cut) * it->second.second;		
			prev_cut = it->first;	
			tree.erase(it++);
		} else {
			assert(numeric_limits<long long>::max() / (day - it->second.first) >= (prefix_sum[cut_index + 1] - prefix_sum[prev_cut + 1])); 
			res += (day - it->second.first) * (prefix_sum[cut_index + 1] - prefix_sum[prev_cut + 1]) + (cut_index - prev_cut) * it->second.second;			
			break;
		}
	}
	tree[cut_index] = make_pair(day, level);
	return res;
}

long long cut(long long day, long long level) {
	if(get_height(0, day) <= level) return 0;
	int cut_index = find_cut_index(day, level);
	return calc_cutoff(cut_index, day, level);	
}

int main() {
	int m;
	long long d, b;
	read<int>(n); read<int>(m);
	init();
	for(int i = 0; i < m; ++i) {
		read<long long>(d); read<long long>(b);
		printf("%lld\n", cut(d, b));
	}
	return 0;
}