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
111
112
113
114
115
116
117
118
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

struct mh_t{
	int pos;
	long long height;
	long long day;

	bool operator<(const mh_t& that) const {
		return (pos < that.pos);
	}

	mh_t(int p, long long h, long long d) : pos(p), height(h), day(d) {}
};

vector<int> aSorted;
vector<long long> sums;
set<mh_t> mowings;

static inline void calculateSums(int n) 
{
	long long sum = 0;
	for (int i = 0; i < n; ++i) {
		sum += aSorted[i];
		sums.push_back(sum);
	}
}

static inline int findPos(long long d, long long b)
{
	int pos = -1;
	int z = aSorted.size() - 1;
	int a = 0;
	mh_t searchKey(a, b, d);
	set<mh_t>::iterator it;
	long long height;

	searchKey.pos = z;
	it = mowings.lower_bound(searchKey);
	height = it->height + aSorted[searchKey.pos] * (d - it->day);
	if (height >= b) {
		return z;
	}

	searchKey.pos = a;
	it = mowings.lower_bound(searchKey);
	height = it->height + aSorted[searchKey.pos] * (d - it->day);
	if (height <= b) {
		return -1;
	}


	while (z - a > 1) {
		searchKey.pos = (z + a) / 2;
		it = mowings.lower_bound(searchKey);
		height = it->height + aSorted[searchKey.pos] * (d - it->day);
		if (height >= b) {
			a = searchKey.pos;
		} else {
			z = searchKey.pos;
		}
	}

	return a;
}

static long long process(long long d, long long b)
{
	long long result = 0;
	int pos = findPos(d, b);

	if (pos >= 0) {
		int previous = -1;
		for (set<mh_t>::iterator it = mowings.begin(); it != mowings.end(); ++it) {
			if (it->pos <= pos) {
				result += (sums[it->pos] - (previous >= 0 ? sums[previous] : 0)) * (d - it->day) + (it->height - b) * (it->pos - previous);
			} else {
				if (previous < pos) {
					result += (sums[pos] - (previous >= 0 ? sums[previous] : 0)) * (d - it->day) + (it->height - b) * (pos - previous);
				}
				mowings.erase(mowings.begin(), it);
				break;
			}
			previous = it->pos;
		}

		mowings.insert(mh_t(pos, b, d));
	}

	return result;
}

int main() 
{
	int n, m;
	long long d, b;
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; ++i) {
		int a;
		scanf("%d", &a);
		aSorted.push_back(a);
	}
	sort(aSorted.begin(), aSorted.end(), greater<int>());
	calculateSums(n);
	mowings.insert(mh_t(n, 0, 0));

	while (m--) {
		scanf("%lld %lld", &d, &b);
		printf("%lld\n", process(d, b));
	}

	return 0;
}