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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<long long>::iterator up(vector<long long>::iterator beg, vector<long long>::iterator end, long long b, long long d){
vector<long long>::iterator it;
  
  int count = std::distance(beg,end),step;
  while (count>0)
  {
    it = beg; step=count/2; std::advance (it,step);
    if (!(b<*it*d))                 
      { beg=++it; count-=step+1;  }
    else count=step;
  }
  return beg;
}

int main(){
ios_base::sync_with_stdio(0);
long long n,m;
cin>>n>>m;
vector<long long> wzr;
for(int i=0;i<n;++i){long long a; cin>>a; wzr.push_back(a);}
sort(wzr.begin(),wzr.end());
vector<long long> acc(n,0);
acc[n-1]=wzr[n-1];
for(int i=n-2;i>=0;--i){acc[i]=acc[i+1]+wzr[i];}
long long tot_kg=0;
for(int j=0;j<m;++j){

long long b=0,d=0;
cin>>d>>b;

long long it=distance(wzr.begin(),up(wzr.begin(),wzr.end(),b,d));
long long  x;
x=d*acc[it]-b*(n-it); 
if(x-tot_kg>0)x-=tot_kg; else x=0;
cout<<(long long)x<<endl;
tot_kg+=x;
//cout<<tot_kg<<endl;
}
}