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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#include <tuple>
using namespace std;
#define ll long long
#define LL long long
#define PB push_back
#define MT make_tuple
#define TT tuple<int, int, long long, long long>
#define REP(x,n) for(int x = 0; x < n; x++)

vector<int> v;
vector<ll> sum;

ll heigth(int pos, TT a, int d){
	ll delta = ((d - get<2>(a))*v[pos]) + get<3>(a);
	return delta;
	
}

ll cropp(TT a, int d, int h){
	ll s = (get<3>(a) - h)*(get<1>(a)-get<0>(a));
	s += (d - get<2>(a))*sum[get<1>(a)]-sum[get<0>(a)];
	return s;
}

void print(TT p){
	printf("%d %d %lld %lld\n", get<0>(p), get<1>(p), get<2>(p), get<3>(p));
}


int binary_search(int p0, int p1, LL p2, LL p3, int d, int h){
	if (p0 == p1)
		return p1;
	int mid = (p0+p1)/2;
		if (heigth(mid, MT(p0,p1,p2,p3),d)>=h)
			return binary_search(p0,mid,p2,p3,d,h);
		else 
			return binary_search(mid+1, p1,p2,p3,d,h);
}

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	int a;
	REP(x, n){
		scanf("%d", &a);
		v.PB(a);
		sort(v.begin(),v.end());
	}
	ll s = 0;
	sum.PB(0);
	REP(x, n){
		s += v[x];
		sum.PB(s);
	}
	
	//start,end,day,heigth
	stack<tuple<int,int,LL,LL> >cut;
	cut.push(MT(0,v.size(),0,0));
	ll d, h;
//	auto p = cut.top();
//	printf("%d %d %lld %lld\n", get<0>(p), get<1>(p), get<2>(p), get<3>(p));
	TT p;
	REP(x, m){

		ll rslt = 0;
		scanf("%lld%lld", &d, &h);
		do{
			p = cut.top();
			cut.pop();
			rslt += cropp(p,d,h);
					 
		}
		while(heigth(get<0>(p), p, d) > h && get<0>(p) != 0);
		int up= binary_search(get<0>(p), get<1>(p),get<2>(p),get<3>(p),d, h);
		rslt -= cropp(MT(get<0>(p), up, get<2>(p), get<3>(p)),d,h);
		if (up != get<0>(p))
			cut.push(MT(get<0>(p), up, get<2>(p), get<3>(p)));
		if (up != get<1>(p))
			cut.push(MT(up, get<1>(p), d,h));

		printf("%lld\n", rslt);
	}
	return 0;
}