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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
using namespace std;

int n, m;
long long *a, *d, *b;
long long start, stop;
long long *sums;
stack<long long> D, B;
stack<int> S, E;

void init();
long long calc( long long d, long long b, int s, int e);
long long height(long long d, long long b, int e);

int main()
{
	ios_base::sync_with_stdio(false);
	init();
	
	for( int i=0 ; i<m ; i++ ) {
		
		long long difference = 0;
		
		while( !D.empty() && height( D.top(), B.top(), E.top() ) > height( d[i], b[i], E.top() ) ) {
			long long l=-1, r=E.top(), mid;
			while( l+1<r ) {
				mid = (l+r+1)/2;
				if( height( D.top(), B.top(), mid ) > height( d[i], b[i], mid ) )
					r = mid;
				else
					l = mid;				
			}
			if( S.top() >= r ) {
				difference += calc( D.top(), B.top(), S.top(), E.top() );
				D.pop();
				B.pop();
				S.pop();
				E.pop();
			}
			else {
				difference += calc( D.top(), B.top(), r, E.top() );
				E.top() = r-1;
			}			
		}
		if( D.empty() ) {
			D.push(d[i]);
			B.push(b[i]);
			S.push(0);
			E.push(n-1);
			difference -= calc( D.top(), B.top(), S.top(), E.top() );
		} else if( E.top() != n-1 ) {
			D.push(d[i]);
			B.push(b[i]);
			S.push( E.top()+1 );
			E.push(n-1);
			difference -= calc( D.top(), B.top(), S.top(), E.top() );
		}
		
		
		cout << difference << "\n";
	}
	
	
	return 0;
}


void init() {
	cin >> n >> m;
	a = new long long [n];
	for( int i=0 ; i<n ; i++ )
		cin >> a[i];
	sort( a, a+n );
	
	d = new long long [m];
	b = new long long [m];
	for( int i=0 ; i<m ; i++ )
		cin >> d[i] >> b[i];
	start = 0;
	stop = d[m-1];
	
	sums = new long long [n+1];
	sums[0] = 0;
	for( int i=1 ; i<=n ; i++ )
		sums[i] = sums[i-1] + a[i-1];
	
	D.push(0);
	B.push(0);
	S.push(0);
	E.push(n-1);
}

long long calc( long long d, long long b, int s, int e) {
	long long rage = sums[e+1]-sums[s];
	long long field=0;
	field += b * (e-s+1);
	field += rage * (stop - d);
	return field;
}
long long height(long long d, long long b, int e) {
	long long w = b;
	w += (stop-d)*a[e];
	return w;
}