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
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
#include <ext/numeric>
using namespace std ;
using namespace __gnu_cxx ;
typedef long long LL ;
typedef pair<int,int> PII ;
typedef vector<int> VI ;
const int INF = 1e9+100 ;
const LL INFLL = (LL)INF * (LL)INF ;
#define REP(i,n) for(i=0;i<(n);++i)
#define ALL(c) c.begin(),c.end()
#define VAR(v,i) __typeof(i) v=(i)
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i)
#define CLEAR(t) memset(t,0,sizeof(t))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second

template<class T1,class T2> ostream& operator<<(ostream &s, const pair<T1,T2> &x) { s<< "(" << x.FI << "," << x.SE << ")"; return s;}
template<class T>           ostream& operator<<(ostream &s, const vector<T>   &t) { FOREACH(it, t) s << *it << " " ; return s ; }
template<class T>           ostream& operator<<(ostream &s, const set<T>      &t) { FOREACH(it, t) s << *it << " " ; return s ; }
template<class T1,class T2> ostream& operator<<(ostream &s, const map<T1, T2> &t) { FOREACH(it, t) s << *it << " " ; return s ; }

///////////////////////////////////////////

const int MAXX = 1000100 ;

int counter[MAXX+1] ;
LL sum[MAXX+1] ;

struct segment {
	static LL addA ;
	
	LL a_, b ;
	int x, y ;
	segment(LL aa, LL bb, int xx, int yy) : a_(aa), b(bb), x(xx), y(yy) {}
	
	LL getVal(int p) const {
		//assert(x<=p && p<=y) ;
		return (a_+addA)*p + b ;
	}
	LL getLastVal() const {
		return getVal(y) ;
	}
	LL getFirstVal() const {
		return getVal(x) ;
	}
	int getFirstGreater(LL h) const {
		//assert(h<=getLastVal()) ;
		LL a = a_+addA ;
		//assert(a>0) ;
		//assert(h-b>=0) ;
		int ret = ((h-b)+(a-1))/a ;
		//assert(x<ret && ret<=y) ;
		return ret ;
	}
	LL cut(LL h, int p=-INF) const {
		//assert(p<=y) ;
		p = max(p, x) ;
		return (a_+addA)*(sum[y]-sum[p-1]) + (b-h)*(counter[y]-counter[p-1]) ;
	}
} ;
LL segment::addA=0 ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	int n, m, i, x, MAXX=0 ; // przyslania
	cin >> n >> m ;
	REP(i,n) {
		cin >> x ;
		counter[x]++ ;
		MAXX = max(MAXX, x) ;
	}
	for(i=1 ; i<=MAXX ; i++) {
		sum[i] = sum[i-1] + (LL)i*counter[i] ;
		counter[i] += counter[i-1] ;
	}
	
	stack<segment> S ;
	S.push(segment(0,0, 1,MAXX)) ;
	LL d, h, prev_d=0 ;
	while(m--) {
		LL d, h ;
		cin >> d >> h ;
		segment::addA += d-prev_d ;
		prev_d = d ;
		
		if(S.top().getLastVal()<h) cout << 0 << endl ;
		else {
			LL ret = 0 ;
			while(!S.empty() && h<=S.top().getFirstVal()) {
				ret += S.top().cut(h) ;
				S.pop() ;
			}
			if(!S.empty() && h<=S.top().getLastVal()) {
				int l = S.top().getFirstGreater(h) ;
				ret += S.top().cut(h, l) ;
				S.top().y=l-1 ;
			}
			cout << ret << "\n" ; //endl ;
			
			S.push(segment(-segment::addA,h, (S.empty()? 1 : S.top().y+1),MAXX)) ;
		}
	}
}