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

using namespace std;

const int N = 1e6;

vector <int> Wzrost;
long long T_Pref[N];
vector < pair < pair <int,int>, pair<long long,long long> > > K;

inline int Wyszukaj(int p,int k,long long t,long long b,pair <long long,long long> war){
	int s;
	long long a_wys;
	pair <long long,long long> zmiana;
	while(p<k){
		s = (p+k+1)/2;
		a_wys = war.second+(t-war.first)*(long long)Wzrost[s];
		if(a_wys >= b) k = s-1;
		else p = s;
	}
	return p;
}

inline long long S_Pref(int p,int k){
	if(p>k) return 0;
	return T_Pref[k+1]-T_Pref[p];
}

inline void Wczytaj(int n){
	int i,a;
	for(i=0; i<n; i++){
		scanf("%d", &a);
		Wzrost.push_back(a);
	}
}

inline bool Sprawdz(int p,long long t,long long b,pair <long long,long long> war){
	long long a_wys;
	a_wys = war.second+(t-war.first)*(long long)Wzrost[p];
	if(a_wys>= b) return true;
	return false;
}

int main(){
	pair <long long,long long> a_para;
	long long t,b,a_wynik,d;
	int n,m;
	int j,i,x,p,k;
	scanf("%d%d", &n,&m);
	Wczytaj(n);
	sort(Wzrost.begin(),Wzrost.end());
	for(i=0; i<n; i++){
		T_Pref[i+1] = T_Pref[i]+(long long)Wzrost[i];
		K.push_back(make_pair( make_pair(i,i),make_pair(0,0) ));
	}
	for(i=0; i<m; i++){
		scanf("%lld%lld", &t,&b);
		a_wynik = 0;
		while(!K.empty() && Sprawdz( K.back().first.first,t,b,K.back().second ) ) {
			d = (long long)(K.back().first.second)-(long long)(K.back().first.first)+1;
			a_wynik += d*(K.back().second.second-b)+S_Pref(K.back().first.first,K.back().first.second)*(t-K.back().second.first);
			K.pop_back();
		}
		if(K.size()==0) K.push_back(make_pair(make_pair(0,n-1),make_pair(t,b)));
		else{
			p = K.back().first.first; k = K.back().first.second;
			x = Wyszukaj(p,k,t,b,K.back().second);
			x++;
			a_para = K.back().second;
			a_wynik += S_Pref(x,k)*(t-K.back().second.first)-(long long)(k-x+1)*(b-K.back().second.second);
			K.pop_back();
			K.push_back( make_pair( make_pair(p,x-1),a_para ) );
			if(x!=n) K.push_back( make_pair( make_pair(x,n-1), make_pair(t,b) ) );
		}
		printf("%lld\n", a_wynik);
	}
	return 0;
}