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
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

class grassHandler {
private:
	struct signature {
		int idX;
		long long daysLost;
		long long mbase;
		signature(int id, long long d, long long ba): idX(id), daysLost(d), mbase(ba) {};
	};
	long long days;
	vector<int> growRates;
	vector<int> sumGrowRates;
	stack<signature> signatures;

	long long getH(const signature &sig, int idx) {
		return (days - sig.daysLost) * growRates[idx] + sig.mbase;
	}
	long long getHCumul(const signature &sig, int idx) {
		return (days - sig.daysLost) * sumGrowRates[idx] + sig.mbase * (growRates.size() - idx);
	}
	long long getHInterval(const signature &sig, int idx1, int idx2) {
		return (days - sig.daysLost) * (sumGrowRates[idx1] - sumGrowRates[idx2]) + sig.mbase * (idx2 - idx1);
	}
public:
	grassHandler(): days(0) {
		signatures.push(signature(0, 0, 0));
	}
	void addRate(int rate) {
		growRates.push_back(rate);
	}
	void init() {
		sort(growRates.begin(), growRates.end());
		sumGrowRates = growRates;
		for(int i = growRates.size() - 2; i>=0; i--) {
			sumGrowRates[i] += sumGrowRates[i+1];
		}
	}
	void move(long long d) {
		days = d;
	}
	long long chop(long long b) {
		long long ret = 0;
		long long temp;
		int lastIdx = -1;
		while((!signatures.empty()) && (getH(signatures.top(), signatures.top().idX) >= b)) {
			if(lastIdx == -1) {
				temp = getHCumul(signatures.top(), signatures.top().idX);
				temp -= (growRates.size() - signatures.top().idX) * b;
				ret += temp;
			}
			else {
				temp = getHInterval(signatures.top(), signatures.top().idX, lastIdx);		
				temp -= (lastIdx - signatures.top().idX) * b;		
				ret += temp;
			}	
			lastIdx = signatures.top().idX;
			signatures.pop();
		}
		if(signatures.empty()) {
			signatures.push(signature(0, days, b));
			return ret;			
		}
		int lo, hi, mid;
	
	 	lo = signatures.top().idX;
		if(lastIdx = -1)
			hi = growRates.size() - 1;
		else
			hi = lastIdx - 1;

		bool found = false;
		while(lo < hi) {
			mid = (lo + hi) / 2;
			if(getH(signatures.top(), mid) >= b) {
				found = true;
				hi = mid;
			}
			else
				lo = mid + 1;
		}
		if(found) {
			if(lastIdx == -1) {
				temp = getHCumul(signatures.top(), lo);
				temp -= (growRates.size() - lo) * b;
				ret += temp;
			}
			else {
				temp = getHInterval(signatures.top(), lo, lastIdx);		
				temp -= (lastIdx - lo) * b;		
				ret += temp;
			}
			signatures.push(signature(lo, days, b));
			return ret;
		}
		else if(lastIdx == -1)
			return 0;
		else {
			signatures.push(signature(lastIdx, days, b));
			return ret;
		}
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	int N, M;
	grassHandler handler;
	cin >> N;
	cin >> M;
	int temp;
	for(int i=0; i<N; i++) {
		cin >> temp;
		handler.addRate(temp);
	}
	handler.init();
	long long b, d;
	for(int i=0; i<M; i++) {
		cin >> d;
		cin >> b;
		handler.move(d);
		cout << handler.chop(b) << endl;
	}
	return 0;
}