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
#include <cstdio>
#include <algorithm>

using namespace std;

#pragma GCC optimize("Ofast")

int P[ 1000006 ];
int V[ 1000006 ];
long long S[ 1000006 ];

typedef struct {
    long long t,h,p;
} stack_t;
stack_t ST[ 1000006 ];
int ilst = 0;

int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    n++; V[0]=0;
    long long mx_v = 0;
    for ( int i=1; i<n; i++ ) {
        scanf("%d",V+i);
        if ( V[i] > mx_v ) mx_v = V[i];
    }
    sort( V, V+n );
    int wsk = 0;
    for ( int i=0; i<=mx_v; i++ ) {
        while ( V[wsk]<i && wsk<n ) wsk++;
        P[i]=wsk;
    }
    S[n]=0; P[0]=1;
    for ( int i=n-1; i>=0; i-- ) S[i] = S[i+1]+V[i];
    ST[ ilst++ ] = { 0, 0, 0 };
    while ( m-- ) {
        long long h,t;
        scanf("%lld%lld",&t,&h);
        long long last_e = n;
        long long w = 0;
        while ( ilst>1 ) {
            stack_t *s = ST + ilst-1;
            long long dt = t - s->t;
            if ( s->h+dt*V[s->p] < h ) break;
            w += (last_e-s->p)*(s->h-h) + (S[s->p]-S[last_e])*dt;
            last_e = s->p;
            ilst--;
        }
        stack_t *s = ST + ilst-1;
        long long dt = t - s->t;
        long long calc_v = ( h-s->h + dt-1 )/dt;
        if ( calc_v <= mx_v ) {
            long long pp = P[ calc_v ];
            w += (last_e-pp)*(s->h-h) + (S[pp]-S[last_e])*dt;
            if ( calc_v )
                 ST[ilst++] = { t, h, pp };
                else s->t = t;
        } else {
            if ( last_e != n )
               ST[ilst++] = { t, h, last_e };
        }
        printf("%lld\n",w);
    }
    return 0;
}