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
#define DBG false

#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

int n, m;
int speeds[500000];
long long accumulated[500000];

void read_and_sort_speeds() {
  for (int i = 0; i < n; ++i) {
    cin >> speeds[i];
  }
  // desc sort
  sort(speeds, speeds + n, [](int a, int b){return a > b;});
}

void compute_accumulated() {
  accumulated[0] = speeds[0];
  for (int i = 1; i < n; ++i) {
    accumulated[i] = accumulated[i-1] + speeds[i];
    if (DBG) {
      cout << "acc[" << i << "]: " << accumulated[i] << endl;
    }
  }
}

struct cut {
  cut(long long d, long long b, int end): d(d), b(b), end(end) {}
  const long long d;
  const long long b;
  const int end;
};

ostream& operator<<(ostream& os, const cut& c) {
  return os << "cut(" << c.d << ", " << c.b << ", " << c.end << ")";
}

stack<cut> cuts;

int find_first_not_cut(long long d, int begin, const cut& c, long long b) {
  long long days = d - c.d;
  int* bound = upper_bound(speeds + begin, speeds + c.end, b,
      [days, &c](long long b, int speed) {
      return days * speed + c.b < b;
      });
  int result = bound - speeds;
  if (DBG) {
    cout << "last cut: " << d << ", " << begin << ", "
      << c << ", " << b << " -> " << result << endl;
  }
  return result;
}

long long cut_area(long long d, int begin, int end, const cut& c, long long b) {
  if (begin >= end) {
    return 0;
  }
  long long days = d - c.d;
  long long one_day = accumulated[end - 1];
  if (begin > 0) {
   one_day -= accumulated[begin - 0];
  }
  long long result = days * one_day;
  if (DBG) { 
    cout << "cut_area " << d << ", " << begin << ", " << end << ", " << c << ", " << b << endl;
    cout << "one day: " << one_day << ", tmp: " << result << endl;
  }
  long long rect = (long long)(end - begin) * (b - c.b);
  if (DBG) { cout << "rect: " << rect << endl; }
  return result - rect;
}

void compute() {
  for (int i = 0; i < m; ++i) {
    long long area = 0;
    long long d, b;
    cin >> d >> b;
    int first_not_cut = 0;
    while (!cuts.empty()) {
      if (DBG) {
        cout << "while..  d: " << d << ", " << b << ", top: " << cuts.top() << endl;
      }
      int next_first_not_cut = find_first_not_cut(d, first_not_cut, cuts.top(), b);
      // TODO compute area
      area += cut_area(d, first_not_cut, next_first_not_cut, cuts.top(), b);
      //
      first_not_cut = next_first_not_cut;
      if (first_not_cut == cuts.top().end) {
        if (DBG) cout << "pop" << endl;
        cuts.pop();
      } else {
        if (DBG) cout << "break\n";
        break;
      }
    }
    if (DBG) {
      cout << "cuts.empty(): " << cuts.empty() << ", area: " << area
                                  << ", first_not_cut: " << first_not_cut << endl;
    }
    if (area > 0) {
      cuts.push(cut(d, b, first_not_cut));
    }
    cout << area << endl;
  }
}

int main() {
  cin >> n >> m;
  read_and_sort_speeds();
  compute_accumulated();
  cuts.push(cut(0, 0, n));
  compute();
  return 0;
}