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

using namespace std;

struct koszenie {
  int v;
  long long s, h, t;
  koszenie(int v, long long s, long long h, long long t) : v(v), s(s), h(h), t(t) {}
};

int main() {
  int N, T, _;
  _ = scanf("%d%d", &N, &T);
  vector<long long> v(N);
  for (int i = 0; i < N; ++i) {
    _ = scanf("%lld", &v[i]);
  }
  sort(v.begin(), v.end(), greater<long long>());

  vector<long long> sv(N);
  for (int i = 0; i < N; ++i) {
    sv[i] = v[i];
    if (i > 0) {
      sv[i] += sv[i - 1];
    }
  }

  /*  vector<pair<int, int>> koszenia;
  for (int i = 0; i < T; ++i) {
    long long ti = t[i];
    int j = lower_bound(v.begin(), v.end(), h[i], [ti](int v, int h)->bool {return ti*v<h;}) - v.begin();
    while (!koszenia.empty() && koszenia.back().first >= j) {
      koszenia.pop_back();
    }
    koszenia.push_back(make_pair(j, i));
    }*/
  
  vector<koszenie> k;
  for (int i = 0; i < T; ++i) {
    long long h, t;
    _ = scanf("%lld%lld", &t, &h);
    /*
    int vi = v.size() - 1;
    for (; vi >= 0; vi--) {
      int j = k.size() - 1;
      for (; j >= 0; j--) {
	if (k[j].v <= v[vi]) {
	  break;
	}
      }
      int d = 0;
      if (j >= 0) {
	d = v[vi] * k[j].t - k[j].h;
      }
      if (v[vi]*t - d > h) {
	break;
      }
    }
*/
    int vi = lower_bound(v.begin(), v.end(), h, [t,&k](long long v, long long h)->bool{
      int j = upper_bound(k.begin(), k.end(), koszenie(v, 0, 0, 0), [](const koszenie& k1, const koszenie& k2)->bool{return k1.v < k2.v;}) - k.begin();
      j--;
      long long d = 0;
      if (j >= 0) {
	d = v * k[j].t - k[j].h;
      }
      return v * t - d > h;
      }) - v.begin();
    /*
    int vi =0;
    for (; vi < v.size(); vi++) {
      int j = upper_bound(k.begin(), k.end(), koszenie(v[vi], 0, 0, 0), [](const koszenie& k1, const koszenie& k2)->bool{return k1.v < k2.v;}) - k.begin();
      j--;
      int d = 0;
      if (j >= 0) {
	d = v[vi] * k[j].t - k[j].h;
      }
      if (v[vi]*t - d <= h) {
	break;
      }
    }
    */
    vi--;
    if (vi  < 0) {
      printf("0\n");
      continue;
    }
    long long s = 0;
    while (!k.empty() && k.back().v >= v[vi]) {
      s += k.back().s;
      k.pop_back();
    }
    if (k.empty()) {
      long long total = sv[vi]*t - h*(vi+1); 
      printf("%lld\n", total - s);
      k.push_back(koszenie(v[vi], total, h, t));
    } else {
      long long total = sv[vi]*(t-k.back().t) - (h-k.back().h)*(vi+1); 
      printf("%lld\n", total - s);
      k.push_back(koszenie(v[vi], total, h,t));
    }
  }
}