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
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <vector>

#define LAST_ROW_IDX (1 << 19)
#define LAST_ROW_SIZE (1 << 19)
#define TREE_SIZE ((1 << 21) + 1)

typedef long long int i64;

struct T {
    T() : last_d(0), last_b(0), sum_a(0), sum_da(0), sum_b(0), actual(true) {}
    
    i64 last_d;
    i64 last_b;
    
    i64 sum_a;
    i64 sum_da;
    i64 sum_b;
    
    bool actual;
} t[TREE_SIZE];

inline int left(int x) { return 2 * x; }
inline int right(int x) { return 2 * x + 1; }

void propagate_node(int idx, i64 begin, i64 end)
{
    assert(idx < LAST_ROW_IDX + LAST_ROW_SIZE);
    
    t[idx].sum_da = t[idx].last_d * t[idx].sum_a;
    t[idx].sum_b = t[idx].last_b * (end - begin + 1); 
    
    t[idx].actual = true;
    
    t[left(idx)].actual = t[right(idx)].actual = false;
    t[left(idx)].last_d = t[right(idx)].last_d = t[idx].last_d;
    t[left(idx)].last_b = t[right(idx)].last_b = t[idx].last_b;
}

void update_tree(int idx, int begin, int end, int u_begin, int u_end, i64 u_d, i64 u_b)
{
    assert(idx < LAST_ROW_IDX + LAST_ROW_SIZE);
    
    if (u_begin <= begin && end <= u_end) {
        t[idx].last_d = u_d;
        t[idx].last_b = u_b;
        propagate_node(idx, begin, end);
    } else {
        int middle = (begin + end) / 2;
        
        if (!t[left(idx)].actual) propagate_node(left(idx), begin, end);
        if (!t[right(idx)].actual) propagate_node(right(idx), begin, end);
        
        if (u_begin <= middle) {
            update_tree(left(idx), begin, middle, u_begin, u_end, u_d, u_b);
        }
        if (middle < u_end) {
            update_tree(right(idx), middle + 1, end, u_begin, u_end, u_d, u_b);
        }
        
        t[idx].sum_da = t[left(idx)].sum_da + t[right(idx)].sum_da;
        t[idx].sum_b = t[left(idx)].sum_b + t[right(idx)].sum_b;
        
        t[idx].actual = true;
    }
}

T query_tree(int idx, int begin, int end, int q_begin, int q_end)
{
    assert(idx < LAST_ROW_IDX + LAST_ROW_SIZE);
    
    if (!t[idx].actual) propagate_node(idx, begin, end);
    
    if (q_begin <= begin && end <= q_end) {
        return t[idx];
    } else {
        int middle = (begin + end) / 2;
        T l, r, o;
        
        if (q_begin <= middle) l = query_tree(left(idx), begin, middle, q_begin, q_end);
        if (middle < q_end) r = query_tree(right(idx), middle + 1, end, q_begin, q_end);
        
        o.sum_a = l.sum_a + r.sum_a;
        o.sum_b = l.sum_b + r.sum_b;
        o.sum_da = l.sum_da + r.sum_da;
        
        return o;
    }
}

i64 n, m, a;
i64 d, b;
std::vector<i64> sorted_a;

int binary_search()
{
    int begin = 0, end = n - 1, middle;
    int o = n;
    T q;
    
    while (begin <= end) {
        middle = (begin + end) / 2;
        q = query_tree(1, 0, LAST_ROW_SIZE - 1, middle, middle);
        if (d * q.sum_a - q.sum_da + q.sum_b > b) {
            o = middle;
            end = middle - 1;
        } else {
            begin = middle + 1;
        }
    }
    
    return o;
}

int main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a);
        sorted_a.push_back(a);
    }
    std::sort(sorted_a.begin(), sorted_a.end());
    for (int i = 0; i < n; i++) {
        t[LAST_ROW_IDX + i].sum_a = sorted_a[i];
    }
    for (int i = LAST_ROW_IDX - 1; i > 0; i--) {
        t[i].sum_a = t[left(i)].sum_a + t[right(i)].sum_a;
    }
    for (int i = 0; i < m; i++) {
        scanf("%lld%lld", &d, &b);
        int bs = binary_search();
        if (bs == n) {
            printf("0\n");
        } else {
            T q = query_tree(1, 0, LAST_ROW_SIZE - 1, bs, n - 1);
            printf("%lld\n", d * q.sum_a - q.sum_da + q.sum_b - (n - bs) * b);
            update_tree(1, 0, LAST_ROW_SIZE - 1, bs, n - 1, d, b);
        }
    }
    return 0;
}