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
#include <stdint.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


struct Cut {
  int64_t d, b;
  int p;
  
  Cut(): d(0), b(0), p(0) { }
  Cut(int64_t const &d, int64_t const &b, int const &p): d(d), b(b), p(p) { }
  ~Cut() { }
};


int last_cut(vector<Cut> const &cuts, int const &p) { // last cut where c.p <= p
  int l0 = 0;
  int l1 = cuts.size() - 1;
  
  if(cuts[l1].p <= p) return l1;
  if(not (cuts[l0].p <= p)) return -1; // damn impossible
  
  while(l1 != l0) {
    int lh = (l0 + l1 + 1) / 2;
    
    if(cuts[lh].p <= p) l0 = lh;
    else l1 = lh - 1;
  }
  
  return l0;
}


bool is_sufficient(Cut const &c, vector<int64_t> const &growth, int const &p, vector<Cut> const &cuts) {
  int l = last_cut(cuts, p);
  int64_t val = cuts[l].b + (c.d - cuts[l].d) * growth[p];
  return val > c.b;
}


int first_sufficient(Cut const &c, vector<int64_t> const &growth, vector<Cut> const &cuts) {
  int p0 = 0;
  int p1 = growth.size() - 1;
  
  if(is_sufficient(c, growth, p0, cuts)) return p0;
  if(not is_sufficient(c, growth, p1, cuts)) return p1 + 1;
  
  while(p1 != p0) {
    int ph = (p0 + p1) / 2;
    
    if(is_sufficient(c, growth, ph, cuts)) p1 = ph;
    else p0 = ph + 1;
  }
  
  return p0;
}


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int n, m;
  cin >> n >> m;
  
  vector<int64_t> growth(n);
  for(int i = 0; i < n; ++i) cin >> growth[i];
  sort(growth.begin(), growth.end());
  
  vector<int64_t> gSum(n+1);
  gSum[n]   = 0;
  gSum[n-1] = growth[n-1];
  for(int i = n - 2; i >= 0; --i) gSum[i] = growth[i] + gSum[i + 1];
  
  // cerr << "growth = "; for(int i = 0; i < n; ++i) cerr << growth[i] << ' '; cerr << '\n';
  // cerr << "gSum   = "; for(int i = 0; i < n; ++i) cerr << gSum[i]   << ' '; cerr << '\n';
  
  vector<Cut> cuts;
  
  cuts.push_back(Cut());
  
  for(int j = 0; j < m; ++j) {
    Cut c;
    cin >> c.d >> c.b;
    
    c.p = first_sufficient(c, growth, cuts);
    
    // cerr << "p = " << c.p << '\n';
    
    int64_t r = 0;
    int prevP = n;
    while(not cuts.empty() and cuts.back().p >= c.p) {
      r += cuts.back().b * (prevP - cuts.back().p) + (c.d - cuts.back().d) * (gSum[cuts.back().p] - gSum[prevP]) - c.b * (prevP - cuts.back().p);
      // cout << "removing cut " << cuts.back().d << ' ' << cuts.back().b << ' ' << cuts.back().p << '\n';
      prevP = cuts.back().p;
      cuts.pop_back();
    }
    
    if(not cuts.empty()) {
      r += cuts.back().b * (prevP - c.p) + (c.d - cuts.back().d) * (gSum[c.p] - gSum[prevP]) - c.b * (prevP - c.p);
    }
    
    cuts.push_back(c);
    
    cout << r << '\n';
  }
  
  return 0;
}