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
94
#include <iostream>
#include <vector>
#include <algorithm>

struct Frame {
    unsigned length;
    unsigned long long time;
    unsigned long long height;

    Frame(unsigned length, unsigned long long time, unsigned long long height):
        length(length), time(time), height(height) {}

    friend std::ostream & operator << (std::ostream & out, Frame const& F) {
        return out << "(" << F.length << ", " << F.time << ", " << F.height << ")";
    }
};

std::vector<unsigned long long> A;
std::vector<unsigned long long> pref;

unsigned long long at(unsigned idx, Frame const& F, unsigned long long time) {
    return F.height + A[idx] * (time - F.time);
}

unsigned long long delta(unsigned begin, unsigned end) {
    unsigned long long res = 0;
    if(end != 0) res += pref[end - 1];
    if(begin != 0) res -= pref[begin - 1];
    return res;
}

unsigned get_division(unsigned first, unsigned end, Frame const& F, unsigned long long d, unsigned long long b) {
    unsigned orig_first = first;

    if(at(first, F, d) < b) return 0;

    while(end - first > 1) {
        unsigned middle = (end + first) / 2;
        if(at(middle, F, d) < b) end = middle;
        else first = middle;
    }

    return end - orig_first;
}

unsigned split(std::vector<Frame> & S, unsigned long long d, unsigned long long b, unsigned long long & res) {
    unsigned cnt = 0;
    while(!S.empty() && at(cnt + S.back().length - 1, S.back(), d) >= b) {
        Frame & F = S.back();
        res += F.length * F.height + delta(cnt, cnt + F.length) * (d - F.time) - F.length * b;
        cnt += F.length;
        S.pop_back();
    }

    if(!S.empty()) {
        Frame & F = S.back();
        unsigned dp = get_division(cnt, cnt + F.length, F, d, b);
        res += dp * F.height + delta(cnt, cnt + dp) * (d - F.time) - dp * b;
        F.length -= dp;
        cnt += dp;
    }

    return cnt;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    unsigned n, m;
    std::cin >> n >> m;

    for(unsigned i = 1; i <= n; i++) {
        long long unsigned x;
        std::cin >> x;
        A.push_back(x);
    }

    std::sort(std::begin(A), std::end(A), std::greater<decltype(A)::value_type>());
    std::partial_sum(std::begin(A), std::end(A), std::back_inserter(pref));

    std::vector<Frame> S;
    S.emplace_back(n, 0, 0);

    for(unsigned q = 1; q <= m; q++) {
        unsigned long long d, b;
        unsigned long long res = 0;

        std::cin >> d >> b;
        unsigned cnt = split(S, d, b, res);

        if(cnt > 0) S.emplace_back(cnt, d, b);

        std::cout << res << std::endl;
    }
}