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
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

typedef long long ll;

#define poka(x) cerr << #x << " = " << x << endl;

class trojka{
public:	
	int ind;
	ll dzien, wys;
	trojka(int ind, ll dzien, ll wys){
		this->ind = ind;
		this->dzien = dzien;
		this->wys = wys;
	}
	void pokaz(){
		cerr << "(ind = " << ind << ", dzien = " << dzien << ", wys = " << wys << ")\n";
	}
};

ll sp[500*1000+9];

ll sumana(int a, int b){
	if(a > b) return 0;
	if(a==0) return sp[b];
	return sp[b]-sp[a-1];
}

int main(){
	ios_base::sync_with_stdio(0);	
	int traw, dni;
	cin >> traw >> dni;
	vector<ll> wzrost(traw);
	for(int i = 0; i < traw; ++i) cin >> wzrost[i];
	sort(wzrost.begin(), wzrost.end());
	sp[0] = wzrost[0]; 
	for(int i = 1; i < traw; ++i) sp[i] = sp[i-1] + wzrost[i];
	stack<trojka> stos;
	stos.push(trojka(0,0,0));
	while(dni--){
		ll dzien, wys;
		cin >> dzien >> wys;
		int prawy = traw;
		ll suma = 0;
		while(!stos.empty()){
			int ind = stos.top().ind;
			ll czas = dzien - stos.top().dzien;
			ll wyswtedy = stos.top().wys;
			ll wysteraz1 = wyswtedy + czas * wzrost[ind];
			if(wysteraz1 > wys){
				suma += czas * sumana(ind, prawy-1) + 
						(wyswtedy - wys) * ll(prawy - ind);
				prawy = ind;
				stos.pop();
			}
			else{
				int a = ind, b = prawy;
				while(a < b){
					int m = (a+b)/2;
					ll wysteraz = wyswtedy + czas * wzrost[m];
					if(wysteraz <= wys) a = m+1;
					else b = m;
				}
				if(a != traw) stos.push(trojka(a, dzien, wys));
				suma += czas * sumana(a, prawy-1) + 
						(wyswtedy - wys) * ll(prawy - a);
				break;
			}
		}
		if(stos.empty()) stos.push(trojka(0,dzien,wys));
		cout << suma << "\n";
	}
	return 0;
}