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
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;
#define pb push_back
#define bk back()
#define si size()
#define lf(x) ((x)<<1)
#define ri(x) (lf(x)+1)

const int maxn=500005;

struct seg{
    ll h, t;
    int p, q;
    seg(int a, int b, ll c, ll d)
        : p(a), q(b), h(c), t(d) {}
};

ll a[maxn];
ll p[maxn];

inline ll diff(seg s, ll d, ll b, int x){
    return (d-s.t)*a[x]+s.h-b;
}

int binSearch(seg s, ll d, ll b){
    while(s.p<=s.q){
        int m=(s.p+s.q)/2;
        if(diff(s, d, b, m)>0)
            s.q=m-1;
        else s.p=m+1;
    }
    return s.q+1;
}

inline ll sum(int a, int b){
    return p[b]-((a>0)?p[a-1]:0);
}

inline ll cutSum(int p, int q, ll h, ll t, ll d, ll b){
    return (sum(p, q)*(d-t))+(h-b)*(q-p+1);
}

int main()
{
    ll d, b;
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;++i)
        scanf("%lld", a+i);
    sort(a, a+n);
    p[0]=a[0];
    for(int i=1;i<n;++i)
        p[i]=p[i-1]+a[i];
    vector<seg> S;
    S.pb(seg(0, n-1, 0, 0));
    while(m--){
        ll res=0;
        scanf("%lld%lld", &d, &b);
        while(!S.empty() && diff(S.bk, d, b, S.bk.p)>0){
            res+=cutSum(S.bk.p, S.bk.q, S.bk.h, S.bk.t, d, b);
            S.pop_back();
        }
        if(S.empty())
            S.pb(seg(0, n-1, b, d));
        else{
            int x=binSearch(S.bk, d, b);
            if(x<n){
                res+=cutSum(x, S.bk.q, S.bk.h, S.bk.t, d, b);
                S.bk.q=x-1;
                S.pb(seg(x, n-1, b, d));
            }
        }
        printf("%lld\n", res);
    }
}