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
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <stack>
using namespace std;

typedef long long ll;

const int N_MAX = 5e5+10;
const int T_MAX = 3*N_MAX;

struct node {
  ll start, last_d, last_b;
  
  node(ll s, ll ld, ll lb) : start(s), last_d(ld), last_b(lb) {}

  void debug() {
    cerr << "node (" << start << ", " << last_d << ", " << last_b << ")\n";
  }
};

int n, m;
ll a[N_MAX];
ll d, b;

stack<node> s;
ll sum_tree[T_MAX];

void build_sum_tree(int i, int x, int y) {
  if (x == y) {
    sum_tree[i] = a[x];
  } else {
    int mid = (x+y) / 2;
    build_sum_tree(2*i, x, mid);
    build_sum_tree(2*i+1, mid+1, y);
    sum_tree[i] = sum_tree[2*i] + sum_tree[2*i+1];
  }
}

ll val_sum_tree(int i, int l, int r, int x, int y) {
  if (x > y) return 0;
  if (l == x && r == y) return sum_tree[i];

  int mid = (l+r) / 2;
  ll res = 0;
  res += val_sum_tree(2*i, l, mid, x, min(y, mid));
  res += val_sum_tree(2*i+1, mid+1, r, max(mid+1, x), y);
  
  return res;
}

ll sum_between(ll x, ll y) {
  ll res = (x < n) ? val_sum_tree(1, 0, n-1, x, y-1) : 0;
  // cerr << "sum_between(" << x << ", " << y << ") = " << res << '\n';
  return res;
}

ll sum_between_slow(ll x, ll y) {
  ll res = 0;
  for (int i = x; i < y; i++) {
    res += a[i];
  }
  cerr << "sum_between_slow(" << x << ", " << y << ") = " << res << '\n';
  return res;
}

ll find_k_slow(ll x, ll y, ll t_last_b, ll t_last_d) {
  for (ll k = x; k < y; k++) {
    if (t_last_b + (d - t_last_d) * a[k] > b) return k;
  }
  return y;
}

ll find_k(ll x, ll y, ll t_last_b, ll t_last_d) {
  ll count = y-x, step;

  while (count > 0) {
    // cerr << "find_k " << x << " " << (x+count) << '\n';
    step = count / 2;
    ll mid = x + step;
    if (!(b < t_last_b + (d - t_last_d) * a[mid])) {
      x = mid+1;
      count -= step+1;
    } else {
      count = step;
    }
  }
  return x;
}

int main() {
  s.push(node(-1, 0, 0));
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%lld", a+i);
  sort(a, a+n);
  build_sum_tree(1, 0, n-1);

  for (int qq = 0; qq < m; qq++) {
    scanf("%lld %lld", &d, &b);
    // cerr << "> " << d << " " << b << '\n';

    ll ans = 0;
    ll k = n, r = n;
    while (!s.empty()) {
      node t = s.top();
      // t.debug();
      if ((t.start == -1) || (t.last_b + (d - t.last_d) * a[t.start] <= b)) {
        // cerr << "part\n";
        // k = find_k_slow(t.start + 1, r, t.last_b, t.last_d);
        k = find_k(t.start + 1, r, t.last_b, t.last_d);
        ans += t.last_b * (r-k) + (d - t.last_d) * sum_between(k, r) - (r-k) * b;
        // cerr << "ans=" << ans << '\n';
        break; 
      } else {
        // cerr << "full\n";
        s.pop();
        k = t.start;
        // cerr << "k..r=" << k << " " << r << '\n';
        ans += t.last_b * (r-k) + (d - t.last_d) * sum_between(k, r) - (r-k) * b;
        // cerr << "ans=" << ans << '\n';
        r = k;
      }
    }

    if (k < n) s.push(node(k, d, b));
    printf("%lld\n", ans);
  }
  return 0;
}