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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
/*
 * Created by Mieszko Mazurek
 * on 29.09.2015
 */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>



#define __inline__ 		__attribute__((always_inline)) inline

#define getchar()			getc_unlocked(stdin)
#define putchar(c) 		putc_unlocked(c, stdout)

#define sint					signed int
#define uint 					unsigned int

#define UINT_MIN			0
#define UINT_MAX 			0xFFFFFFFF
#define SINT_MIN			-0x90000000
#define SINT_MAX			0x8FFFFFFF

#define	bool					unsigned char
#define true					1
#define false					0


__inline__
void writeuint(uint val)
{
	static char buffer[16];
	register uint len, c;
	
	len = 0;
	
	if (val) {
		while (val) {
			c = val % 10 + '0';
		
			buffer[len++] = c;
		
			val /= 10;
		}
		
		while(len)
			putchar(buffer[--len]);
	}
	else
		putchar('0');
}


__inline__
void writeuintln(uint val)
{
	writeuint(val);
	putchar('\n');
}


__inline__
uint readuint()
{
	uint val;
	char c;
	

	do c = getchar();	
	while (c < '0' || c > '9');

	val = c - '0';
	c = getchar();

	while (c >= '0' && c <= '9') {
		val *= 10;
		val += c - '0';
		
		c = getchar();
	}
	
	return val;
}



int uintcomparator(const void *a, const void *b)
{
	return *((int*) a) > *((int*) b);
}


uint n, m, *a, *swapped;

uint calc_day_hay(uint days, uint mowing)
{
	register uint i, height;
	auto uint hay;
	
	hay = 0;
	
	for (i = n - 1; i != UINT_MAX; i--) {
		height = a[i] * days + swapped[i];
		
		if (height > mowing) {
			hay += height - mowing;

			swapped[i] = mowing;
		}
		else
			swapped[i] = height;
	}
	
	return hay;
}


int main(int argc, char** argv)
{
	register uint i;
	auto uint day, lastday, mowing, *hay;

	n = readuint();
	m = readuint();
	
	a = malloc(n * sizeof(uint));
	for (i = 0; i < n; i++)
		a[i] = readuint();
	
	qsort(a, n, sizeof(uint), uintcomparator);
	
	swapped = malloc(n * sizeof(uint));
	memset(swapped, 0, n * sizeof(uint));
	
	lastday = 0;
	
	hay = malloc(m * sizeof(uint));
	
	for (i = 0; i < m; i++) {
		day = readuint();
		mowing = readuint();
		
		hay[i] = calc_day_hay(day - lastday, mowing);
		
		lastday = day;
	}
	
	for (i = 0; i < m; i++)
		writeuintln(hay[i]);
	
	free(swapped);
	free(hay);
	free(a);

	return 0;
}