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

struct cut {
  int pos;
  long long time;
  long long h;
};

long long grow[500001];
long long pref[500001];
vector<cut> V;

cut findh(int i) {
  int p = 0;
  int q = V.size()-1;
  while (p < q) {
    int s = (p+q+1)/2;
    if (V[s].pos <= i) {
      p = s;
    } else {
      q = s-1;
    }
  }

  return V[p];
}

int binsearch(int p, int q, long long t, long long h) {
  while (p<q) {
    int s = (p+q)/2;
    cut lastcut = findh(s);
    
    if (lastcut.h + (t - lastcut.time) * grow[s] > h) {
      q = s;
    } else {
      p = s+1;
    }
  }

  return p;
}

int main() {
  int n;
  int m;
  scanf("%d%d", &n, &m);

  for(int i = 0; i < n; i++) {
    scanf("%lld", &grow[i]);
  }

  sort(grow, grow+n);

  pref[0] = grow[0];

  for (int i = 0; i < n; i++) {
    pref[i] = pref[i-1] + grow[i];
  }

  cut temp;
  temp.pos = 0;
  temp.time = 0;
  temp.h = 0;
  V.push_back(temp);

  for (int i = 0; i < m; i++) {
    long long t;
    long long h;
    scanf("%lld%lld", &t, &h);
    int k = binsearch(0, n, t, h);
    long long res = 0;
    int q = n;

    while (V.size() > 0 && V[V.size()-1].pos >= k) {
      cut temp = V[V.size()-1];
      V.pop_back();
      res += (temp.h-h)*(q-temp.pos) + (t-temp.time)*((q > 0 ? pref[q-1] : 0) - (temp.pos > 0 ? pref[temp.pos-1] : 0));
      q = temp.pos;
    }
    cut temp = V[V.size()-1];
    res += (temp.h-h)*(q-k) + (t-temp.time)*((q > 0 ? pref[q-1] : 0) - (k > 0 ? pref[k-1] : 0));

    printf("%lld\n", res);

    temp.h = h;
    temp.pos = k;
    temp.time = t;
    V.push_back(temp);
  }

return 0;
}