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
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
const long long N=500000;
typedef map<long long,long long> iim; iim mm;
iim::iterator ii(long long x){return --mm.upper_bound(x);}
long long lv(long long x){return ii(x)->second;}
long long n,m,a[N],sr[N],i,d,b,pd=0,pb=0,pc=0,dd,l,r,v,c,q;
long long val(long long x){return (x>=pc?pb:lv(x))+dd*a[x];}
int main(){
    scanf("%lld%lld",&n,&m);
    for(i=0;i<n;++i)scanf("%lld",a+i);
    sort(a,a+n);
    sr[n-1]=a[n-1];for(i=n-2;i>=0;--i)sr[i]=sr[i+1]+a[i];
    mm[0]=0;
    for(i=0;i<m;++i){
        scanf("%lld%lld",&d,&b);
        dd=d-pd;
        l=0;r=n-1;
        while(r-l>1){
            c=(r+l)/2;v=val(c);
            if(v>b)r=c;else l=c;
        }
        c=val(l)>b?l:r;
        q=sr[c]*dd-(b-pb)*(n-c);
        printf("%lld\n",q);
        if(c>pc)mm[c]=b-val(c);
        else if(c<pc)mm.erase(++ii(pc),mm.end());
        pc=c;pb=b;pd=d;
    }
    return 0;
}