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 <vector>
#include <iostream>
#include <algorithm>

//#define DEBUG_LOGGING

#ifdef DEBUG_LOGGING
#include <stdio.h>
#include <assert.h>
#endif

using namespace std;

struct Cut {
	Cut(int pos, long long time, long long height) : pos(pos), time(time), height(height) {}

	bool operator<(const Cut &rhs) const { return pos < rhs.pos; }

	int pos;
	long long time, height;
};

int main() {
	std::ios_base::sync_with_stdio(false);

	int field_size, cut_counts;
	cin >> field_size >> cut_counts;

	vector<int> speeds(field_size);
	for(int n = 0; n < field_size; n++)
		cin >> speeds[n];
	std::sort(speeds.begin(), speeds.end());

	vector<long long> speed_sums(field_size + 1);
	speed_sums.back() = 0;
	for(int n = field_size - 1; n >= 0; n--)
		speed_sums[n] = speed_sums[n + 1] + speeds[n];

	vector<Cut> cuts;
	cuts.push_back(Cut(0, 0, 0));

#ifdef DEBUG_LOGGING
	printf("Sums: ");
	for(int n = 0; n < (int)speeds.size(); n++)
		printf("%d ", speeds[n]);
	printf("\n");
#endif

	long long time = 0;
	vector<long long> field(field_size, 0ll);
	for(int c = 0; c < cut_counts; c++) {
		long long cur_time, cut_height;
		cin >> cur_time >> cut_height;

#ifdef DEBUG_LOGGING
		printf("cut: %lld %lld\n", cur_time, cut_height);
#endif
		long long sum = 0;
		int new_pos = 0, last_pos = field_size;

		while(!cuts.empty()) {
			const Cut &last_cut = cuts.back();
			int min_pos = last_cut.pos, max_pos = last_pos;
			long long growth_time = cur_time - last_cut.time;

			if(last_cut.height + growth_time * speeds[last_pos - 1] <= cut_height)
				break;

			while(min_pos < max_pos) {
				int mid_pos = (min_pos + max_pos) / 2;
				long long height = last_cut.height + growth_time * speeds[mid_pos];
#ifdef DEBUG_LOGGING
				printf("mid: %d (%lld)\n", mid_pos, height);
#endif
				if(height >= cut_height)
					max_pos = mid_pos;
				else
					min_pos = mid_pos + 1;
			}

			if(min_pos == last_pos)
				break;

#ifdef DEBUG_LOGGING
			printf("prev cut: %d %lld %lld | min: %d last: %d\n", last_cut.pos, last_cut.time,
				   last_cut.height, min_pos, last_pos);
			printf("growth: %lld * %lld\n", growth_time,
				   (speed_sums[min_pos] - speed_sums[last_pos]));
#endif

			sum += growth_time * (speed_sums[min_pos] - speed_sums[last_pos]);
			sum += last_cut.height * (last_pos - min_pos);
			sum -= cut_height * (last_pos - min_pos);

			last_pos = min_pos;
			if(min_pos == last_cut.pos)
				cuts.pop_back();
			else
				break;
		}

		if(last_pos < 0)
			last_pos = 0;
		if(last_pos < field_size)
			cuts.push_back(Cut(last_pos, cur_time, cut_height));

#ifdef DEBUG_LOGGING
		long long slow_sum = 0;
		{
			long long growth_mul = cur_time - time;
			time = cur_time;

			for(int n = 0; n < field_size; n++) {
				long long height = field[n] + growth_mul * speeds[n];
				if(height > cut_height) {
					slow_sum += height - cut_height;
					height = cut_height;
				}
				field[n] = height;
			}
		}

		printf("sum: %lld slow: %lld\n", sum, slow_sum);
		assert(sum == slow_sum);
#endif
		cout << sum << endl;
	}

	return 0;
}