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
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <sstream>
#include <cmath>
using namespace std;

typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<int,int> pii;
#define mp make_pair

#define REP(i,n) for (int i=0,___=(n); i<___; ++i)
#define FOR(i,a,b) for (int i=(a),___=(b); i<=___; ++i)
#define FORD(i,a,b) for (int i=(a),___=(b); i>=___; --i)

int read() { int n; scanf("%d", &n); return n; }
ll readl() { ll n; scanf("%lld", &n); return n; }

struct Node {
    int a, b;
    ll d, h;
    Node(int aa = 0, int bb = 0, ll dd = 0, ll hh = 0) : a(aa), b(bb), d(dd), h(hh) {}
};

int main() {

    int n = read();
    int m = read();
    vi v(n);

    REP(i, n) v[i] = read();
    sort(v.begin(), v.end());

    vll s(n+1);
    s[0] = 0;
    REP(i, n) s[i+1] = s[i] + v[i];

    vector<Node> vv;
    vv.push_back(Node(0, n, 0, 0));

    REP(nr, m) {
        ll dd = readl();
        ll hh = readl();
        ll res = 0;
        int ri = n;
        while (!vv.empty()) {
            Node &x = vv.back();
            if (x.h + (dd - x.d) * v[x.a] > hh) {
                ll h1 = x.h * (x.b - x.a) + (s[x.b] - s[x.a]) * (dd - x.d);
                ll h2 = hh * (x.b - x.a);
                res += h1 - h2;
                ri = x.a;
                vv.pop_back();
                continue;
            }
            if (x.h + (dd - x.d) * v[x.b - 1] <= hh) break;
            int a = x.a, b = x.b;
            while (a + 1 < b) {
                int c = (a + b) / 2;
                if (x.h + (dd - x.d) * v[c] <= hh)
                    a = c;
                else
                    b = c;
            }
            if (x.h + (dd - x.d) * v[a] <= hh)
                ++a;
            ll h1 = x.h * (x.b - a) + (s[x.b] - s[a]) * (dd - x.d);
            ll h2 = hh * (x.b - a);
            res += h1 - h2;
            ri = a;
            x.b = a;
            break;
        }
        if (ri < n)
            vv.push_back(Node(ri, n, dd, hh));
        printf("%lld\n", res);
    }

    return 0;
}