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
#include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

struct trip{
	LL day;
	LL element;
	LL high;
	
	void make_trip(LL a, LL b, LL c){
		day = a;
		element = b;
		high = c;
	}
	
};

#define el element
#define PLL pair<LL, LL>
#define st first
#define nd second
#define mp make_pair
#define PII pair<int, int>
#define mt make_trip

const int mxn = 500007;
const LL INF = 1000000000005LL;

LL t[mxn];
LL suf[mxn];

LL add(LL from, LL to, LL sh, LL eh, LL sd, LL ed){
	if(to < from)
		return 0LL;
	return ((to-from+1)*(sh-eh))+((suf[from] - suf[to+1])*(ed-sd));
}

LL BS(LL from, LL to, LL sh, LL eh, LL sd, LL ed){
	while(from < to){
		LL sred = (from + to)/2LL;
		if(sh + (ed - sd)*t[sred] <= eh)
			from = sred+1;
		else
			to = sred;
	}
	return from;
}

int main() {
	
	LL n, m;
	scanf("%lld %lld", &n, &m);
	for(int i=1; i<=n; ++i)
		scanf("%lld", &t[i]);
	t[n+1] = INF;
	sort(t+1, t+n+1);
	
	for(int i=n; i>=0; --i)
		suf[i] = suf[i+1] + t[i];
	
	deque <trip> Q;
	trip X;
	X.mt(0LL, 0LL, 0LL);
	Q.push_back(X);

	while(m--){
		LL day, high;
		scanf("%lld %lld", &day, &high);
		
		trip k = Q.back();
		trip last;
		last.mt(day, n+1, high);
		
		LL result = 0LL;
		while((day - k.day)*t[k.el] + k.high > high){
			Q.pop_back();
			result+= add(k.el, last.el-1, k.high, high, k.day, day);
			last = k;
			k=Q.back();
		}
		
		LL where = BS(k.el, last.el, k.high, high, k.day, day);
		result+= add(where, last.el-1, k.high, high, k.day, day);
		printf("%lld\n", result);
		
		X.mt(day, where, high);
		Q.push_back(X);
		
	}
	
	return 0;
}