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
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
//Daniel Grzegorzewski
#include <bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ST first
#define ND second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef long long LL;

const int N = 5*(int)1e5 + 10;
const int SQ = 710;

int n, m, kiedy[N], lvl[N], a[N], ki[SQ], lv[SQ], suf[N];
int d, b;
bool git[SQ];

void re(int i)
{
	int co = i/SQ;
	if (kiedy[i] < ki[co]) {
		kiedy[i] = ki[co];
		lvl[i] = lv[co];
	}
}

int bins(int v)
{
	int x1 = 0, x2 = n-1, x3;
	while (x2-x1 > 1) {
		x3 = (x1+x2)/2;
		re(x3);
		if (lvl[x3]+(d-kiedy[x3])*a[x3] > v)
			x2 = x3;
		else
			x1 = x3;
	}
	re(x1);
	if (lvl[x1]+(d-kiedy[x1])*a[x1] > v)
		return x1;
	re(x2);
	if (lvl[x2]+(d-kiedy[x2])*a[x2] > v)
		return x2;
	return -1;
}

#undef int
int main()
{
#define int long long
    scanf("%lld%lld", &n, &m);
    for (int i = 0; i < n; ++i) 
    	scanf("%lld", &a[i]);
    for (int i = 0; i < SQ; ++i)
    	git[i] = true;
    sort(a, a+n);
    for (int i = n-1; i >= 0; --i)
    	suf[i] = suf[i+1] + a[i];
    while (m--) {
    	scanf("%lld%lld", &d, &b);
    	int kt = bins(b);
    	if (kt == -1) {
    		printf("0\n");
    		continue;
    	}
    	int lim, res = 0;
    	if (kt%SQ == 0)
    		lim = kt;
    	else
    		lim = kt+(SQ-kt%SQ);
    	lim = min(lim, n);
    	int wsk = kt/SQ;
    	if (lim != kt)
    		git[wsk] = false;
    	for (int i = kt; i < lim; ++i) {
    		re(i);
    		res += lvl[i]+(d-kiedy[i])*a[i]-b;
    		kiedy[i] = d;
    		lvl[i] = b;
    	}
    	for (int i = lim; i < n; i += SQ) {
    		int nr = i/SQ;
    		if (git[nr]) {
    			int spr = SQ;
    			if (i+SQ >= n)
    				spr = n-i;
    			res += (suf[i]-suf[i+spr])*(d-ki[nr])+spr*(lv[nr]-b);
    			ki[nr] = d;
    			lv[nr] = b;
    			continue;
    		}
    		for (int j = i; j < min(n, i+SQ); ++j) {
    			re(j);
    			res += lvl[j]+(d-kiedy[j])*a[j]-b;
    			kiedy[j] = ki[nr];
    			lvl[j] = lv[nr];
    		}
    		git[nr] = true;
    		ki[nr] = d;
    		lv[nr] = b;
    	}
    	printf("%lld\n", res);
    }
}