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
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
#include<map>
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define all(c) (c).begin(),(c).end()
#define scanf(...) scanf(__VA_ARGS__)?:0
#define eprintf(...) fprintf(stderr,__VA_ARGS__),fflush(stderr)
#define e1 first
#define e2 second
#define mp make_pair
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
inline int ceil2(int a){return 1<<((sizeof(int)<<3)-__builtin_clz(a));}
int n,m,s,temp,x[500001],lk[500001];
ll ss[500002],w[500001];
pll z[500001];
pii tree[1048576];
stack<int,vector<int> >stos;
void zmien(int a,int b,int s,int nr=1,int z1=1,int z2=ceil2(n-1))
{
	if (a==z1 && b==z2)
	{
		tree[nr].e1=tree[nr].e2=s;
		return;
	}
	int sr=(z1+z2)>>1;
	if (a<=sr) zmien(a,min(b,sr),s,nr<<1,z1,sr);
	if (b>sr) zmien(max(a,sr+1),b,s,(nr<<1)+1,sr+1,z2);
	tree[nr].e2=max(tree[nr].e1,tree[(nr<<1)+1].e2);
}
int znajdz(int a,int b,int zm=0,int nr=1,int z1=1,int z2=ceil2(n-1))
{
	if (z1==z2)
	{
		int ost=max(zm,tree[nr].e1);
		if (z[ost].e2+(z[temp].e1-z[ost].e1)*x[a]<=z[temp].e2) return -1;
		return a;
	}
	zm=max(zm,tree[nr].e1);
	int sr=(z1+z2)>>1;
	if (b<=sr) return znajdz(a,b,zm,nr<<1,z1,sr);
	if (a>sr) return znajdz(a,b,zm,(nr<<1)+1,sr+1,z2);
	int ost=max(zm,tree[nr<<1].e2);
	if (z[ost].e2+(z[temp].e1-z[ost].e1)*x[sr]<=z[temp].e2) return znajdz(sr+1,b,zm,(nr<<1)+1,sr+1,z2);
	else return znajdz(a,sr,zm,nr<<1,z1,sr);
}
int main()
{
	scanf("%d%d",&n,&m);
	FOR(i,1,n) scanf("%d",&x[i]);
	sort(x+1,x+n+1);
	FORD(i,n,1) ss[i]=ss[i+1]+x[i];
	FOR(i,1,m)
	{
		scanf("%lld%lld",&z[i].e1,&z[i].e2); temp=i;
		lk[i]=znajdz(1,n);
		if (lk[i]==-1){ puts("0"); continue; }
		zmien(lk[i],n,temp);
		while (!stos.empty() && lk[i]<=lk[stos.top()]) w[i]+=w[stos.top()],stos.pop();
		ll wyn=stos.empty()?z[i].e1*ss[lk[i]]:((z[i].e1-z[stos.top()].e1)*ss[lk[i]]+z[stos.top()].e2*(n-lk[i]+1));
		wyn-=z[i].e2*(n-lk[i]+1);
		printf("%lld\n",(ll)(wyn-w[i]));
		stos.push(i);
		w[i]=wyn;
	}
}