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
#include<algorithm>
#include<cstdio>
#include<stack>

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

using namespace std;

struct info {
  long long p, t, count;
  info() {}
  info(long long p, long long t, long long count) : p(p), t(t), count(count) {}
};

stack<info> S;
long long a[500001];
long long pref[500001];

info m_info;

bool find_grass(long long const& speed, pair<long long, long long> const& time_height) {
  return speed * (time_height.first - m_info.t) + m_info.p < time_height.second;
}

template<class S>
void compute_pref_sum(S * in, int lenght, S * out) {
  out[0] = in[0];
  FOR(i, 1, lenght) {
    out[i] = out[i - 1] + in[i];
  }
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  REP(i, n) {
    scanf("%lld", a + i + 1);
  }
  a[0] = 0;
  sort(a + 1, a + n + 1);
  compute_pref_sum(a, n + 1, pref);
  S.push(info(0, 0, n));
  REP(i, m) {
    long long t, h, acc = 0, acc_sum = 0;
    scanf("%lld%lld", &t, &h);
    while (!S.empty()) {
      info inf = S.top();
      if (inf.p + (t - inf.t) * a[1 + n - acc - inf.count] >= h) {
        S.pop();
        acc_sum += inf.p * inf.count +
            (pref[n - acc] - pref[n - acc - inf.count]) * (t - inf.t) -
            h * inf.count;
        acc += inf.count;
      } else break;
       
    }
    if (!S.empty()) {
      m_info = S.top();
      long long * start = a + (n - acc - m_info.count) + 1;
      int idx =
          lower_bound(start, start + m_info.count, make_pair(t, h), find_grass)
              - start;
      acc_sum += m_info.p * (m_info.count - idx) +
          (pref[n - acc] - pref[n - acc - (m_info.count - idx)]) *
              (t - m_info.t) -
          h * (m_info.count - idx);
      info n_info(h, t, m_info.count - idx + acc);
      m_info.count = idx;
      S.pop();
      S.push(m_info);
      if (n_info.count > 0) {
        S.push(n_info);
      }
    } else {
      S.push(info(h, t, n));
    }
    printf("%lld\n", acc_sum);
  }
  return 0;
}