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
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
unsigned long long n, m;
unsigned long long trawa[500001];
unsigned long long sumaTraw[500001];
unsigned d, h;
class Grupa{
public:
	unsigned long long min, max, day, h;
	Grupa(unsigned long long argMin, unsigned long long argMax, unsigned long long argDay, unsigned long long argH):
		min(argMin), max(argMax), day(argDay), h(argH){

	}
};

struct classcomp {
	bool operator() (const Grupa & lhs, const Grupa & rhs) const {
		return lhs.min < rhs.min;
	}
};
typedef set <Grupa, classcomp> mySet;
typedef mySet::iterator myIterator;
mySet grupy;
Grupa targetG(0,0,0,0);

void find_group(unsigned long long x){
	targetG.min = x;
	myIterator it = grupy.upper_bound(targetG);
	--it;
	targetG = *it;
}

bool is_cutted(unsigned long long x){
	find_group(x);
	unsigned long long liczbaDni = (d-targetG.day);
	unsigned long long wysokosc = liczbaDni * trawa[x] + targetG.h;
	return wysokosc>h;
}

unsigned long long find_lowest_cutting_index(unsigned long long bottom, unsigned long long top){
	if(bottom == top){
		if(is_cutted(bottom)){
			return bottom;
		}else
			return n;
	}
	unsigned mid = (bottom + top) >> 1;
	if(is_cutted(mid)){
		return find_lowest_cutting_index(bottom, mid);
	} else{
		return find_lowest_cutting_index(mid+1, top);
	}
}
unsigned long long count_hair(unsigned min, unsigned max, unsigned day, unsigned height){
	unsigned long long cut = sumaTraw[max] - sumaTraw[min] + trawa[min];
	cut *= (d - day);
	cut += height * (max - min + 1);
	cut -= h * (max - min + 1);
	return cut;
}

unsigned long long chop_groups(unsigned long long x){
	unsigned long long zgolone = 0;
	myIterator it = grupy.upper_bound(targetG);
	--it;
	myIterator it2 = it;
	zgolone = count_hair(x,it2->max,it2->day,it2->h);
	++it2;
	while(it2!=grupy.end()){
		zgolone += count_hair(it2->min,it2->max,it2->day,it2->h);
		++it2;
	}
	targetG = *it;
	grupy.erase(it,grupy.end());

	if(targetG.min<x){
		Grupa g(targetG.min,x-1,targetG.day,targetG.h);
		grupy.insert(g);
	}
	targetG.min=x;
	targetG.max=n-1;
	targetG.h = h;
	targetG.day = d;
	grupy.insert(targetG);
	return zgolone;
}

int main () {
	ios_base::sync_with_stdio(0);
	cin >> n >> m;
	for(unsigned long long i = 0;i<n;++i)
		cin >> trawa[i];
	sort(trawa,trawa+n);
	sumaTraw[0] = trawa[0];
	for(unsigned long long i = 1;i<n;++i)
		sumaTraw[i] = trawa[i] + sumaTraw[i-1];

	Grupa g (0,n-1,0,0);

	grupy.insert(g);

	for(unsigned long long i = 0;i<m;++i){
		cin >> d >> h;
		unsigned long long x = find_lowest_cutting_index(0,n-1);
		if(x == n){
			cout << "0\n";
			continue;
		}
		cout << chop_groups(x) << "\n";
	}

	return 0;
}