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
#include<bits/stdc++.h>

using namespace std; 

const int mx = 500005; 

long long int suf[mx]; 
long long int t[mx];
int n; 

int bin ( int b, int e, long long int s, long long int r ) { 
	int m = (b+e)/2;
	if ( t[m]*r == s ) { 
		while ( (t[m]*r) == s ) 
			m++; 
		return m; 
	}
	if ( b == e-1 && t[m]*r != s ) 
		return n;
	else if ( s > (t[m]*r) ) 
		return  bin(m,e,s,r); 
	return bin(b,m,s,r); 
}

int main () {
	int q; 
	scanf("%d%d",&n,&q); 
	for ( int i = 1; i <= n; i++ )
		scanf("%d",&t[i]); 
	sort(t,t+n); 
	for ( int i = n; i > 0; i-- ) 
		suf[i] = t[i]+suf[i+1];
	long long int prev = 0; 
	while ( q-- ) { 
		long long int a, b;
		scanf("%lld%lld",&a,&b); 
		int w = bin(0,n,b,a); 
		long long int y = suf[w];
		long long int x = n-w+1; 
		x*=b; 
		y*=a;
		if ( y-( x+ prev ) < 0 ) 
			puts("0"); 
		else {  
			y = (y-(x+prev)); 
			printf("%lld\n",y);
		prev += y;
		}
	}
}