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
#include <iostream>
#include <stdio.h>
#include <sstream>
#include <stdlib.h>
using namespace std;

long long i,j,n,m,s=0,d,e=0,b,l;
long long a[500000+1];
long long p[500000+1];
long long q[500000+1];
long long dd[500000+1];
long long bb[500000+1];
int compare(const void *a,const void *b)
{
return *(long long *)b - *(long long *)a;
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string line;
istringstream ss;
getline(cin,line);
ss.str(line);
ss >> n >> m;

getline(cin,line);
ss.str(line);
ss.clear();
i=1;
while (ss >> l)
{
a[i]=l;
p[i]=0;
q[i]=0;
i++;
}

qsort(&a[1],n,sizeof(long long),compare);



for (j=0;j<m;++j)
{
cin >> dd[j] >> bb[j];
}

for (j=0;j<m;++j)
{
s=0;
d=dd[j];
b=bb[j];

for (i=1;i<=n;++i)
{
long long del=(d-q[i])*a[i];
long long pd=p[i]+del;
if (pd >= b){s+=pd-b;p[i]=b;q[i]=d;} else break;
}
cout <<s<< endl;
}
return 0;
}