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

using namespace std;

const int MAXN = 500005;

struct Level {
  int start;
  long long day;
  long long height;
  Level() {}
  Level(int _start, long long _day, long long _height): start(_start), day(_day), height(_height) {}
};

int n, m;
int a[MAXN];
long long prefSum[MAXN];
vector<Level> S;

inline long long intSum(int x, int y) {
  if (x == 0) {
    return prefSum[y];
  } else {
    return prefSum[y] - prefSum[x-1];
  }
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  sort(a, a+n);
  prefSum[0] = a[0];
  for (int i = 1; i < n; ++i) {
    prefSum[i] = prefSum[i-1] + a[i];
  }
  S.push_back(Level(0, 0, 0));
  for (int i = 0; i < m; ++i) {
    long long d, b, res = 0;
    scanf("%lld%lld", &d, &b);
    // szukamy pierwszego przedzielonego
    int ind = n;
    while (!S.empty()) {
      long long delta = (d - S.back().day);
      long long firstHeight = S.back().height + delta*a[S.back().start];
      if (firstHeight < b) {
        // poszukajmy pierwszego z lewej na przedziale [S.back().first, ind)
        int l = S.back().start, r = ind-1, found = ind;
        while (l <= r) {
          int mid = (l+r) / 2;
          if (S.back().height + delta*a[mid] >= b) {
            found = mid;
            r = mid - 1;
          } else {
            l = mid + 1;
          }
        }
        res += (ind - found) * S.back().height;
        res += intSum(found, ind-1) * delta;
        ind = found;
        break;
      } else {
        res += (ind - S.back().start) * S.back().height;
        res += intSum(S.back().start, ind-1) * delta;
        ind = S.back().start;
        S.pop_back();
      }
    }
    if (ind < n) {
      S.push_back(Level(ind, d, b));
    }
    res -= (n - ind) * b;
    printf("%lld\n", res);
  }
  return 0;
}