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

using namespace std;

int search(vector<int> growth, int begin, int end, long long day, long long h);

int main() {
	int n, m, tmp;
	scanf("%d %d\n", &n, &m);
	
	vector<int> growth;
	
	for(int i=0; i<n; i++) {
		scanf("%d ", &tmp);
		growth.push_back(tmp);
	}
	
	sort(growth.begin(), growth.end());
	
	vector<long long> combined_growth;
	combined_growth.push_back(0);
	
	for(int i=0; i<n; i++) {
		combined_growth.push_back(growth[i]+combined_growth[i]);
	}
	
	long long day, h, prev = 0, result;
	int index;
	
	for(int i=0; i<m; i++) {
		scanf("%lld %lld\n", &day, &h);

		if(day*growth[0] >= h) index = -1;
		else if(day*growth.back() <= h) index = n-1;
		else index = search(growth, 0, n-1, day, h);
		index++;

		result = day*(combined_growth.back()-combined_growth[index]) - h*(n-index) - prev;
		if(result < 0) result = 0;
		prev += result;
		printf("%lld\n", result);
	}
	
	return 0;
}

int search(vector<int> growth, int begin, int end, long long day, long long h) {
	if(end-begin < 2) {
		if(day*growth[end] <= h) return end;
		else return begin;
	}
	
	int mid = (begin + end)/2;
	
	if(day*growth[mid] <= h) return search(growth, mid, end, day, h);
	else return search(growth, begin, mid, day, h);
}