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

using ll = long long int;

struct interval
{
	int begin, end;
	ll cut_day;
	ll above;
};


int interval_search(std::vector<interval> const &_intervals, int _i_size, int _idx)
{
	int low = 0, high = _i_size - 1;
	while (low < high) {
		int mid = low + (high - low) / 2;
		if (_intervals[mid].end < _idx) {
			low = mid + 1;
		} else {
			high = mid;
		}
	}
	return low;
}

int value_search(std::vector<int> const &_a, ll _d, ll _b, std::vector<interval> const &_intervals, int _i_size)
{
	int low = 0, high = _a.size() - 1;
	while (low < high) {
		int mid = low + (high - low) / 2;
		int i_idx = interval_search(_intervals, _i_size, mid);
		ll val = static_cast<ll>(_a[mid]) * (_d - _intervals[i_idx].cut_day) + _intervals[i_idx].above;
		if (!(_b < val)) {
			low = mid + 1;
		} else {
			high = mid;
		}
	}
	return low;
}


int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n, m;
	std::cin >> n >> m;

	std::vector<int> a(n + 1);
	for (int i = 0; i < n; ++i) {
		std::cin >> a[i];
	}
	a[n] = 1000001;
	std::sort(a.begin(), a.end());
	
	std::vector<ll> sums(n + 1);
	sums[0] = 0;
	for (int i = 0; i < n; ++i) {
		sums[i + 1] = sums[i] + a[i];
	}

	int i_end = 0;
	std::vector<interval> intervals(n);
	intervals[i_end++] = { 0, n - 1, 0, 0 };

	ll d, b;
	for (int i = 0; i < m; ++i) {
		std::cin >> d >> b;
		int cut_idx = value_search(a, d, b, intervals, i_end);
		if (cut_idx == n) {
			std::cout << 0 << std::endl;
			continue;
		}
		int i_idx = interval_search(intervals, i_end, cut_idx);
		ll ans = 0;
		ans += (sums[intervals[i_idx].end + 1] - sums[cut_idx]) * (d - intervals[i_idx].cut_day);
		ans -= (intervals[i_idx].end - cut_idx + 1) * (b - intervals[i_idx].above);
		for (int j = i_idx + 1; j < i_end; ++j) {
			ans += (sums[intervals[j].end + 1] - sums[intervals[j].begin]) * (d - intervals[j].cut_day);
			ans -= (intervals[j].end - intervals[j].begin + 1) * (b - intervals[j].above);
		}
		if (intervals[i_idx].begin == cut_idx) { // correct interval
			intervals[i_idx].end = n - 1;
			intervals[i_idx].cut_day = d;
			intervals[i_idx].above = b;
		} else { // split interval
			intervals[i_idx++].end = cut_idx - 1;
			intervals[i_idx] = { cut_idx, n - 1, d, b };
		}		
		i_end = i_idx + 1;

		std::cout << ans << std::endl;
	}

	return 0;
}