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
#include<bits/stdc++.h>
#define rep(i,k,n) for(int i= (int) k;i< (int) n;i++)
#define pb push_back
#define ft first
#define sd second
typedef long long ll;
const long long inf = 9223372036854775807ll;
const int iinf = 2147483647;
const int limit = 1048576;
using namespace std;
bool sync_with_stdio (bool sync = false);

ll sim[limit], ext[limit];

struct seg
{
    ll x1, x2,
        a, b;

    seg(ll x1, ll x2, ll a, ll b)
    :x1{x1},
    x2{x2},
    a{a},
    b{b} { }

    ll cnt()
    {
        return -(a * (ext[x2] - ext[max(x1 - 1, 0ll)]) + b * (sim[x2] - sim[max(x1 - 1, 0ll)]));
    }
    ll intersect(ll a1, ll b1)
    {
        if(b1 - b >= x1 * (a - a1))
            return (b1 - b) / (a - a1);
        return -inf;
    }
};

int main(){
    ll n, m, t1; scanf("%lld%lld", &n, &m);
    rep(i, 0, n)
    {
        scanf("%lld", &t1);
        sim[t1]++; ext[t1] += t1;
    }
    rep(i, 1, limit)
    {
        sim[i] += sim[i - 1]; ext[i] += ext[i - 1];
    }

    vector<seg> border = {seg(-limit, limit - 1, 0, 0)};
    rep(i, 0, m)
    {
        ll sum_under_border = 0;
        ll d, b; scanf("%lld%lld", &d, &b);
        while(true)
        {
            seg s = border.back(); border.pop_back();
            sum_under_border += s.cnt();
            ll c = s.intersect(-d, b);
            if(c >= limit)
            {
                border.pb(s);
                break;
            }
            if(c != -inf)
            {
                seg s1 = seg(s.x1, c, s.a, s.b), s2 = seg(c + 1, limit - 1, -d, b);
                sum_under_border -= s1.cnt();
                printf("%lld\n", s2.cnt() - sum_under_border);
                border.pb(s1); border.pb(s2);
                break;
            }
        }
    }
    return 0;
}