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
81
82
83
84
85
86
87
88
89
90
91
//Aleksander Łukasiewicz
#include<bits/stdc++.h>
using namespace std;

#define fru(j,n) for(int j=0; j<(n); ++j)
#define tr(it,v) for(typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define ALL(G) (G).begin(),(G).end()

typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int INF = 1000000009;
const int MAXN = 500000;

int n;
int tab[MAXN + 3];
LL suf[MAXN + 3];
stack< pair<int, pair<LL,LL> > > cuts;

inline LL interval(int a, int b){
    return suf[a] - suf[b+1];
}

inline LL grow(int ind, LL time, LL add){
    return add + time*tab[ind];
}

int binsearch(int beg, int end, LL height, LL time, LL add){
    while(beg + 1 < end){
        int mid = (beg + end)/2;
        if(grow(mid, time, add) > height)
            end = mid;
        else
            beg = mid;
    }
    
    return end;
}

int main(){
    int Q;
    scanf("%d %d", &n, &Q);
    for(int i=0; i<n; i++)
        scanf("%d", &tab[i]);
    
    sort(tab, tab+n);
    for(int i=n-1; i>=0; i--)
        suf[i] = suf[i+1] + tab[i];
    cuts.push(mp(0, mp(0,0)));
    
    while(Q--){
        LL d, h;
        scanf("%lld %lld", &d, &h);
        LL ans = 0;
        int prev = n;
        while(!cuts.empty()){
            int ind = cuts.top().x;
            LL cuttime = cuts.top().y.x;
            LL cutheight = cuts.top().y.y;
            
            if(grow(ind, d-cuttime, cutheight) < h)
                break;
            
            ans += interval(ind, prev-1)*(d-cuttime) + (cutheight - h)*(prev-ind);
            cuts.pop();
            prev = ind;
        }
        
        int ind; LL cuttime, cutheight;
        if(cuts.empty())
            cuttime = cutheight = ind = 0;
        else
            ind = cuts.top().x, cuttime = cuts.top().y.x, cutheight = cuts.top().y.y;
        
        int cutplace = binsearch(ind-1, prev, h, d-cuttime, cutheight);
        ans += interval(cutplace, prev-1)*(d-cuttime) + (cutheight - h)*(prev - cutplace);

        if(cutplace < n)
            cuts.push(mp(cutplace, mp(d, h)));
        
        printf("%lld\n", ans);
    }
    
    
return 0;
}