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
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define N 500007

long long int vel[N];
long long int sum[N] = {0};
int n;

struct pref {
	int end;	/* last affected piece */
	long long int t;/* time of cut */
	long long int h;/* height of cut */
} Q[N];
int top;

struct pref base_cut;

long long int height(long long int t, struct pref *p)
{
	return p->h + (t - p->t) * vel[p->end];
}

long long int cut(long long int d, long long int b)
{
	int s = 0, e, c;
	long long int res = 0, prev = -1, su, part;
	struct pref *last;

	while (top && height(d, &Q[top]) > b) {
		assert(d >= Q[top].t);
		assert(Q[top].end >= prev);
		if (prev >= 0)
			su = sum[prev];
		else
			su = 0;
		assert(sum[Q[top].end] >= su);

		part = (d - Q[top].t) * (sum[Q[top].end] - su) +
			(Q[top].h - b) * (Q[top].end - prev);
		if (part > 0)
			res += part;

		assert(res >= 0);
		prev = Q[top].end;
		s = Q[top--].end;
	}

	last = top ? &Q[top] : &base_cut;
	e = last->end;

	++top;
	Q[top].t = d;
	Q[top].h = b;

	c = (e + s)/2;
	while (e - s > 1) {
		c = (e + s)/2;
		if (last->h + (d - last->t) * vel[c] > b)
			s = c;
		else
			e = c;
	}

	Q[top].end = e;
	assert(d >= last->t);
	assert(e >= prev);
	if (prev >= 0)
		su = sum[prev];
	else
		su = 0;

	assert(sum[e] >= su);
	part = (d - last->t) * (sum[e] - su) +
		(last->h - b) * (e - prev);
	if (part > 0)
		res += part;

	return res;
}

static int cmp(const void *p1, const void *p2)
{
	return *(const long long int *)p2 - *(const long long int *)p1;
}

int main()
{
	int m, i;
	long long int d, b;

	scanf("%d%d", &n, &m);

	for (i = 0; i < n; ++i) {
		scanf("%lld", &vel[i]);
	}

	qsort(vel, n, sizeof(long long int), cmp);
	base_cut.end = n-1;
	base_cut.t = 0;
	base_cut.h = 0;

	sum[0] = vel[0];
	for (i = 1; i < n; ++i)
		sum[i] = sum[i - 1] + vel[i];

	top = 0;
	for (i = 0; i < m; ++i) {
		scanf("%lld%lld", &d, &b);
		printf("%lld\n", cut(d, b));
	}

	return 0;
}