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
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PI;
typedef long long LL;
typedef double D;
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define R(I,N) for(int I=0;I<N;I++)
#define F(I,A,B) for(int I=A;I<B;I++)
#define FD(I,N) for(int I=N-1;I>=0;I--)
#define make(A) scanf("%d",&A)
#define make2(A,B) scanf("%d%d",&A,&B)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define db if(1)printf
template<typename C> void MA(C& a,C b){if(a<b)a=b;}
template<typename C> void MI(C& a,C b){if(a>b)a=b;}
const int MAX = 1<<19;
int n,nn,m;
int s[MAX];
LL tu[MAX*2],hu[MAX*2];
LL a[MAX*2],b[MAX*2];
bool cz[MAX*2];
LL tnij2(int nr,LL t,LL h,int sze){
  LL res = a[nr] * t + b[nr] - sze * h;
  b[nr] -= res;
  tu[nr] = t;
  hu[nr] = h;
  cz[nr] = 1;
  return res;
}
LL t,h;
LL wyn;
bool tnij(int nr=1,int po=0,int ko=nn){
  if((t - tu[nr])*s[ko-1]+hu[nr] >= h){
    wyn += tnij2(nr,t,h,(ko-po));
    return 1;
  }
  if(po+1==ko)return 0;
  if(cz[nr]){
    tnij2(nr*2,tu[nr],hu[nr],(ko-po)/2);
    tnij2(nr*2+1,tu[nr],hu[nr],(ko-po)/2);
    cz[nr] = 0;
  }
  if(tnij(nr*2,po,(po+ko)/2))
    tnij(nr*2+1,(po+ko)/2,ko);
  b[nr] = b[nr*2] + b[nr*2+1];
  return 0; 
}
main(){
  make2(n,m);
  nn=1;while(nn <= n)nn*=2;
  R(i,n)make(s[i]);
  sort(s,s+n,greater<int>());
  R(i,n)
    a[i+nn] = s[i];
  FD(i,nn)
    a[i] = a[i*2] + a[i*2+1];
  R(i,m){
    scanf("%lld%lld",&t,&h);
    wyn = 0;
    tnij();
    printf("%lld\n",wyn);
  }
}