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
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>		//UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>		//do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;

#define MR 500010

LL pre[MR];
int a[MR];

struct magic
{
	LL base, prevD;
	int ind;
};

vector <magic> V;

int main()
{
	magic wartownik;
	wartownik.base = wartownik.prevD = wartownik.ind = 0;
	V.push_back(wartownik);

	int n, m;
	scanf("%d%d", &n, &m);
	FORQ(i,1,n) scanf("%d", &a[i]);
	sort(a+1, a+n+1);
	FORQ(i,1,n) pre[i] = a[i] + pre[i-1];

	wartownik.ind = n;
	V.PB(wartownik);

	REP(c,m)
	{
		LL b, d;
		scanf("%lld%lld", &d, &b);
		LL res = 0;

		while(!V.empty())
		{
			if(V.back().base + (d-V.back().prevD)*a[V.back().ind] > b)	// cos rosnie
			{
				assert(V.size() > 1);
				// spr czy rosnie w calej grupie
				int pos;
				if(b <= V.back().base)
				{
					pos = V[V.size()-2].ind+1;
				}
				else
				{
					int pom = (b-V.back().base)/(d-V.back().prevD);
					assert(V.back().base + (d-V.back().prevD)*pom <= b);
					assert(V.back().base + (d-V.back().prevD)*(pom+1) > b);
					pos = upper_bound(a+V[V.size()-2].ind+1, a+V.back().ind+1, pom) - a;
				}
				
				if(pos == V[V.size()-2].ind+1)	// w calej grupie rosnie
				{
					assert(pos > 0);
					pos--;
					int ile = V.back().ind - pos;
					res += ile*V.back().base + (pre[V.back().ind]-pre[pos])*(d-V.back().prevD) - ile*b;
					V.pop_back();
				}
				else	// rosnie tylko w czesci
				{
					pos--;
					int ile = V.back().ind - pos;
					res += ile*V.back().base + (pre[V.back().ind]-pre[pos])*(d-V.back().prevD) - ile*b;
					V.back().ind = pos;
					wartownik.base = b;
					wartownik.prevD = d;
					assert(wartownik.ind == n);
					V.PB(wartownik);
					break;
				}
			}
			else	//nic nie rosnie
			{
				if(V.back().ind < n)	// dodaj nowa grupe
				{
					wartownik.base = b;
					wartownik.prevD = d;
					assert(wartownik.ind == n);
					V.PB(wartownik);
				}
				break;
			}
		}

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

	return 0;
}