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

int T = 0;
int K = 0;
int W[510000];
long long sumW[510000];

long long D[510000];
long long H[510000];

int cutIdx[1001000];

int countW[1001000];


struct Cut_t
{
	Cut_t() {};
	Cut_t(int inPosX, long long inH, long long inD) : posX(inPosX), H(inH), D(inD) {}

	int       posX;
	long long H;
	long long D;
};

Cut_t CutTab[510000];
int lastCut = -1;


int compr(const void *a, const void *b)
{
	return (*(int*)a - *(int*)b);
}

int main()
{
	int cnt = 0;

	scanf("%i %i", &T, &K);

	for (int i = 0; i < T; i++)
	{
		scanf("%i", &W[i]);
	}
	W[T] = 1000001;

	for (int i = 0; i < K; i++)
	{
		scanf("%lld %lld", &D[i], &H[i]);
	}
	
	for (int i = 0; i <= 1000001; i++)
	{
		countW[0] = 0;
	}

	for (int i = 0; i <= T; i++)
	{
		countW[W[i]]++;
	}

	int w = 0;
	for (int i = 0; i <= 1000001; i++)
	{
		for (int j = 0; j < countW[i]; j++)
		{
			W[w] = i;
			w++;
		}
	}
	//qsort(W, T, sizeof(int), compr);

	sumW[T] = 0;
	for (int i = T - 1; i >= 0; i--)
	{
		sumW[i] = sumW[i + 1] + W[i];
	}

	w = 0;
	for (int i = 0; i < 1000001; i++)
	{
		while (W[w] < i)
		{
			w++;
		}
		cutIdx[i] = w;
	}

	lastCut = 0;
	CutTab[lastCut] = Cut_t(0, 0, 0);

	for (int i = 0; i < K; i++)
	{
		long long res = 0;

		int posX = T;

		while (1)
		{
			Cut_t cut = CutTab[lastCut];
			long long DD = D[i] - cut.D;
			long long diffH = H[i] - cut.H;

			if (cut.H + DD * W[cut.posX] >= H[i]) // CUT ALL
			{
				res += (sumW[cut.posX] - sumW[posX]) * DD - diffH * (posX - cut.posX);
				posX = cut.posX;
				lastCut--;
				if (lastCut == -1)
				{
					lastCut = 0;
					CutTab[lastCut] = Cut_t(posX, H[i], D[i]);
					break;
				}
			}
			else
			{
				long long idx = (diffH + (DD - 1)) / DD;
				if (idx >= 1000001)
				{
					break;
				}
				int newPosX = cutIdx[(diffH + (DD - 1)) / DD];

				res += (sumW[newPosX] - sumW[posX]) * DD - diffH * (posX - newPosX);

				lastCut++;
				CutTab[lastCut] = Cut_t(newPosX, H[i], D[i]);
				break;
			}
		}

		printf("%lld\n", res);
	}

	return 0;
}