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
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <utility>
#include <stack>
#include <numeric>

using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define MP make_pair
#define FOR(v,p,k) for(auto v=(p);v<=(k);++v)
#define FORD(v,p,k) for(auto v=(p);v>=(k);--v)
#define REP(i,n) for(auto i=0;i<(n);++i)
#define VAR(v,i) __typeof(i) v=(i)
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i)
#define PB push_back
#define ST first
#define ND second
#define SIZE(x) (int)x.size()
#define ALL(c) c.begin(),c.end()

#define ODD(x) ((x)%2)
#define EVEN(x) (!(ODD(x)))

int main() {
  ios_base::sync_with_stdio(0);

  int n, m;
  cin >> n >> m;

  vector<LL> sz(n);

  REP(i,n) {
    cin >> sz[i];
  } 
  sort(ALL(sz));

  vector<LL> suf_sz = sz;
  partial_sum(suf_sz.rbegin(), suf_sz.rend(), suf_sz.rbegin());
  //guards
  sz.push_back(0LL);
  suf_sz.push_back(0LL);

  vector<pair<LL,LL>> trims(m);

  REP(i,m) {
    cin >> trims[i].first >> trims[i].second;
  }

  stack<PII> last_trim;

  REP(t,m) {
    LL d = trims[t].first;
    LL b = trims[t].second;

    LL res{};

    int last_trimmed_pos = n;
    while (!last_trim.empty()) {
      auto index = last_trim.top().first;
      auto trim_nr = last_trim.top().second;

      auto delta_d = d - trims[trim_nr].first;
      auto old_b = trims[trim_nr].second;
      if (sz[index] * delta_d + old_b >= b) {
        LL cnt = last_trimmed_pos - index;
        auto delta_suf_sz = suf_sz[index] - suf_sz[last_trimmed_pos];
        res += cnt * (old_b - b) + delta_d * delta_suf_sz;

        last_trimmed_pos = index;
        last_trim.pop();
      } else {
        auto it = lower_bound(sz.begin()+index, sz.begin()+last_trimmed_pos, 42LL, [&](LL x, LL dummy) {
            return (x * delta_d + old_b) < b;
            });
        auto pos = it - sz.begin();
        LL cnt = last_trimmed_pos - pos;
        auto delta_suf_sz = suf_sz[pos] - suf_sz[last_trimmed_pos];
        res += cnt * (old_b - b) + delta_d * delta_suf_sz;

        if (pos != n)
          last_trim.push(make_pair(pos, t));
        last_trimmed_pos = pos;
        break;
      }
    }
    if (last_trim.empty()) {
        auto it = lower_bound(sz.begin(), sz.begin()+last_trimmed_pos, 42LL, [&](LL x, LL dummy) {
            return (x * d) < b;
            });
        auto pos = it - sz.begin();
        LL cnt = last_trimmed_pos - pos;
        auto delta_suf_sz = suf_sz[pos] - suf_sz[last_trimmed_pos];
        res += cnt * (0LL - b) + d * delta_suf_sz;


        if (pos != n)
          last_trim.push(make_pair(pos, t));
    }
    cout << res << endl;
  }
  cout << flush;
  return 0;
}