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 <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (int i = (a); i <= (b); ++i)
#define REPD(i,a,b) for (int i = (a); i >= (b); --i)
#define FORI(i,n) REP(i,1,n)
#define FOR(i,n) REP(i,0,int(n)-1)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define SZ(x) int((x).size())
#define DBG(v) cerr << #v << " = " << (v) << endl;
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define fi first
#define se second

const int maxn = 1000100;

int a[maxn];
long long pref[maxn];
long long d[maxn], b[maxn];
int last[maxn], pos[maxn];

long long getsum(int low, int high) {
	return pref[high]-pref[low];
}

long long add(int prv, int cur, int left, int right) {
	long long res = (b[prv]-b[cur])*(right-left) + (d[cur]-d[prv])*getsum(left,right);
	//printf("dodaje %lld do wyniku\n", res);
	return res;
}

int main () {
	int n,m,it=0;
	scanf("%d%d", &n, &m);
	FOR(i,n) scanf("%d", &a[i]);
	sort(a,a+n);
	pref[0] = 0;
	FORI(i,n) pref[i] = pref[i-1] + a[i-1];
	last[it] = 0;
	pos[it] = 0;
	d[0] = 0;
	b[0] = 0;
	//m=10;
	//printf("najwyzszy ma %d\n", a[n-1]);
	FORI(i,m) {
		scanf("%lld%lld", &d[i], &b[i]);
		//printf("dzien %lld, wysokosc %lld\n", d[i], b[i]);
		long long res = 0;
		int right = n;
		while (it >= 0) {
			//printf("wyciagam przedzial [%d %d] z dnia %lld (wysokosc %lld)\n", pos[it], right, d[last[it]], b[last[it]]);
			long long left = b[last[it]] + (d[i]-d[last[it]])*a[pos[it]];
			//printf("lewy rosnie o %d\n", a[pos[it]]);
			if (left >= b[i]) {
				//printf("caly bedzie sciety (%lld vs %lld)\n", left, b[i]);
				res += add(last[it], i, pos[it], right);
				right = pos[it];
				it--;
			} else {
				//printf("nie bedzie sciety (%lld vs %lld)\n", left, b[i]);
				break;
			}
		}
		if (it >= 0) {
			//printf("dziele przedzial [%d %d] z dnia %lld (wysokosc %lld, i=%d)\n", pos[it], right, d[last[it]], b[last[it]], last[it]);
			long long thr = b[i] - b[last[it]];
			long long days = d[i] - d[last[it]];
			//printf("szukam granicy dla %lld w %lld dni (%lld na dzien)\n", thr, days, (thr+days-1)/days);
			int q = lower_bound(a+pos[it], a+right, (thr+days)/days) - a;
			//printf("punkt podzialu %d\n", q);
			if (q < n) {
				res += add(last[it], i, q, right);
				it++;
				last[it] = i;
				pos[it] = q;
			}
		} else {
			//printf("skonczyly sie przedzialy\n");
			it++;
			last[it] = i;
			pos[it] = 0;
		}
		printf("%lld\n", res);
	}
}