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
139
140
141
142
143
144
#include <iostream>
#include <stdlib.h>
#include <set>
#include <vector>
#include <assert.h>
#include <algorithm>

typedef long long int int64;
using namespace std;

vector< int > t;
vector< int64 > sum;
int64 currentDay, currentCut;
bool isSearchMode = false;

struct range
{
	int first;
	int count;
	int64 day;
	int64 cut;
	range( int _first, int _count, int64 d, int64 c ) : first( _first ), count( _count ), day( d ), cut( c ) {}
	bool operator < ( const range& other ) const
	{
		if ( isSearchMode )
		{
			if ( other.count )
			{
				return !( other < *this );
			}
			return cut + ( currentDay - day ) * ( int64 ) t[ first + count - 1 ] <= currentCut;
		}

		return first < other.first;
	}
};

int getTIndex( const int& value )
{
	return ( int ) ( &value - &t[ 0 ] );
}

int64 calcCut( const range& r )
{
	const int64 rangeSum = sum[ r.first ] - sum[ r.first + r.count ];
	return rangeSum * ( currentDay - r.day ) + r.count * ( r.cut - currentCut );
}

int main()
{
	int n, m;
	cin >> n >> m;

	t.resize( n );
	for ( int i = 0; i < n; ++i )
	{
		cin >> t[ i ];
	}

	sort( t.begin(), t.end() );

	sum.resize( n + 1 );
	sum[ n ] = 0;
	for ( int i = n - 1; i >= 0; --i )
	{
		sum[ i ] = sum[ i + 1 ] + t[ i ];
	}

	set< range > s;
	s.insert( range( 0, n, 0, 0 ) );
	for ( int i = 0; i < m; ++i )
	{
		cin >> currentDay >> currentCut;

		isSearchMode = true;
		auto it = s.lower_bound( range( 0, 0, 0, 0 ) );
		isSearchMode = false;
		if ( it == s.end() )
		{
			cout << 0 << endl;
		}
		else
		{
			const range& r = *it;

			struct ArrayPred
			{
				int64 dayRange;
				int64 cut;

				ArrayPred( const int64 day, const int64 _cut ) : dayRange( currentDay - day ), cut( _cut ) {}

				bool operator () ( const int& v, const int64& )
				{
					return cut + dayRange * ( int64 ) v <= currentCut;
				}
			};

			auto it2 = lower_bound( t.begin() + r.first, t.begin() + r.first + r.count, currentCut, ArrayPred( r.day, r.cut ) );
			if ( it2 == t.end() )
			{
				cout << 0 << endl;
			}
			else
			{
				int64 cutToday = 0;

				range rCopy = r;

				while ( it != s.end() )
				{
					auto itCopy = it;
					++itCopy;
					s.erase( it );
					it = itCopy;

					if ( it != s.end() )
					{
						cutToday += calcCut( *it );
					}
				}

				if ( it2 == t.begin() + rCopy.first )
				{
					s.insert( range( rCopy.first, rCopy.count, currentDay, currentCut ) );
					cutToday += calcCut( rCopy );
				}
				else
				{
					const int firstPartCount = getTIndex( *it2 ) - rCopy.first;
					assert( firstPartCount );
					cutToday += calcCut( range( rCopy.first + firstPartCount, rCopy.count - firstPartCount, rCopy.day, rCopy.cut ) );

					s.insert( range( rCopy.first, firstPartCount, rCopy.day, rCopy.cut ) );
					s.insert( range( rCopy.first + firstPartCount, rCopy.count - firstPartCount, currentDay, currentCut ) );
				}

				cout << cutToday << endl;
			}
		}
	}

	return 0;
}