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
92
93
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

#define ll long long
const int maxN = 5e5 + 10;
int n, m;
int t[maxN];
ll sums[maxN];

ll sum(int a, int b) { return sums[b] - sums[a - 1]; }

struct Ar {
    ll h, time;
    int from;
    Ar(ll H = -1, ll Time = -1, int From = -1) : h(H), time(Time), from(From) {}
};

vector<Ar>stack;

ll day;

ll H(int i, ll diff, ll h0) {
    return h0 + diff * t[i];
}

// bool verbose;

ll exterminate(ll h) {
    static int q = 0;
    q++;
    /*if(q == 477)
        verbose = true;
    if(verbose)
        printf("executing quest %d...\n", q);*/
    int to = n + 1, from, a, b, avg;
    ll res = 0, diff;
    while(stack.size()) {
        from = stack.back().from;
        /*if(verbose) {
            printf("from begin: %d\n", from);
            printf("stack: ");
            for(Ar& a: stack) printf("{h=%lld time=%lld from=%d} ", a.h, a.time, a.from);
            printf("\n");
        }*/
        diff = day - stack.back().time;
        if(H(from, diff, stack.back().h) < h) {
            a = from, b = to;
            while(b - a - 1) {
//                 if(verbose)
//                     printf("%d %d\n", a, b);
                avg = (a + b) / 2;
                if(H(avg, diff, stack.back().h) < h)
                    a = avg;
                else b = avg;
            }
            from = b;
        }
        /*if(verbose) {
            printf("stack: ");
            for(Ar& a: stack) printf("{h=%lld time=%lld from=%d} ", a.h, a.time, a.from);
            printf("\n");
            printf("in %d: to=%d diff=%lld diffH=%lld SUMMARY=%lld\n", from,
                to, diff, stack.back().h - h, 
               sum(from, to - 1) * diff + (to - from) * (stack.back().h - h));
        }*/
        res += sum(from, to - 1) * diff + (to - from) * (stack.back().h - h);
        to = from;
        if(from == stack.back().from)
            stack.pop_back();
        else break;
    }
    if(from <= n)
        stack.push_back({ h, day, from });
//     verbose = false;
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", t + i);
    sort(t + 1, t + n + 1);
    for(int i = 1; i <= n; ++i)
        sums[i] = sums[i - 1] + t[i];
    stack.push_back({ 0, 0, 1 });
    ll h;
    for(int i = 0; i < m; ++i) {
        scanf("%lld%lld", &day, &h);
        printf("%lld\n", exterminate(h));
    }
    return 0;
}