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
#include <stdio.h>
#include <vector>
#include <stack>
#include <cstdlib>
#include <algorithm>
#include <cmath>

#define ULL64 unsigned long long int

using namespace std;

vector<ULL64> A;
vector<ULL64> Asum;

ULL64 getHay(ULL64 d,ULL64 b)
{
	ULL64 ret=0;
	int imin=0,imax=A.size()-1;

	int idx = -1;

	while(imin<=imax)
	{
		int mid = (imin + imax) / 2;
		if(d*A[mid] == b)
		{
			idx = mid;
			break;
		}

		if(d*A[mid]<b)
		{
			imax = mid-1;
		}
		else
		{
			idx = mid;
			imin = mid+1;
		}
	}

	if(idx!=-1)
	{
		//printf("%lli\n",d*Asum[idx]-b*(idx+1));
		ret = max(d*Asum[idx]-b*(idx+1),(ULL64)0);
	}

	return ret;
}

bool descendingly(ULL64 a,ULL64 b)
{
	return a>b;
}

int main()
{
	int n,m;
	ULL64 a;

	scanf("%i %i",&n,&m);

	for(int i = 0;i<n;i++)
	{
		scanf("%lli",&a);
		A.push_back(a);
	}

	sort(A.begin(),A.end(),descendingly);

	ULL64 tsum = 0;
	for(int i = 0;i<n;i++)
	{
		tsum+=A[i];
		Asum.push_back(tsum);
	}

	ULL64 d,b;
	ULL64 hay;
	ULL64 collectedHay = 0;

	for(int i = 0;i<m;i++)
	{
		scanf("%lli %lli",&d,&b);
		hay = getHay(d,b);
		
		if(hay<collectedHay)
			hay = 0;
		else
			hay = hay-collectedHay;

		printf("%lli\n",hay);

		collectedHay+=hay;
	}
		

	return 0;
}