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
#include <bits/stdc++.h>

using namespace std;

#define PB push_back
#define FORE(i, t) for(typeof(t.begin())i=t.begin();i!=t.end();++i)
#define SZ(x) int((x).size())
#define REP(i, n) for(int i=0,_=(n);i<_;++i)
#define FOR(i, a, b) for(int i=(a),_=(b);i<=_;++i)
#define FORD(i, a, b) for(int i=(a),_=(b);i>=_;--i)

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int INF = 1e9 + 9;

const int MAX_N = 500003;

struct Cut {
    int start;
    ll day, limit;
};

int n, m;
int rates[MAX_N];
ll rates_sums[MAX_N];
vector <Cut> cuts;

bool inline will_cut_something(int cut_start, ll cut_day, ll cut_limit) {
    int a = 0, b = SZ(cuts) - 1;
    while (a <= b) {
        int d = (a + b) / 2;
        Cut *historical_cut = &cuts[d];
        if (historical_cut->start <= cut_start) {
            a = d + 1;
        } else {
            b = d - 1;
        }
    }
    Cut *matching_cut = &cuts[b];
    ll height_before_cutting = matching_cut->limit + (cut_day - matching_cut->day) * (ll) rates[cut_start];
    return cut_limit < height_before_cutting;
}

int inline get_cut_start(ll cut_day, ll cut_limit) {
    int a = 0, b = n - 1;
    while (a <= b) {
        int cut_start = (a + b) / 2;
        if (!will_cut_something(cut_start, cut_day, cut_limit)) {
            a = cut_start + 1;
        } else {
            b = cut_start - 1;
        }
    }
    return a;
}

ll inline compute_harvest(const Cut &old_cut, const Cut &new_cut, int new_cut_end) {
    int new_cut_start = max(old_cut.start, new_cut.start);
    ll were = old_cut.limit * (ll) (new_cut_end - new_cut_start);
    ll growth = (ll) (rates_sums[new_cut_end] - rates_sums[new_cut_start]) * (new_cut.day - old_cut.day);
    ll left = new_cut.limit * (ll) (new_cut_end - new_cut_start);
    return were - left + growth;
}

ll inline make_cut(const Cut &cut) {
    ll harvest = 0;
    int new_cut_end = n;
    while (!cuts.empty() && cuts.back().start >= cut.start) {
        harvest += compute_harvest(cuts.back(), cut, new_cut_end);
        new_cut_end = cuts.back().start;
        cuts.pop_back();
    }
    if (new_cut_end > cut.start) {
        harvest += compute_harvest(cuts.back(), cut, new_cut_end);
    }
    cuts.PB(cut);
    return harvest;
}

void inline one() {
    scanf("%d%d", &n, &m);
    REP (i, n) {
        scanf("%d", rates + i);
    }
    sort(rates, rates + n);
    rates_sums[0] = 0;
    REP(i, n) {
        rates_sums[i + 1] = rates_sums[i] + rates[i];
    }
    cuts.PB((Cut) {0, 0, 0});
    REP (j, m) {
        Cut cut;
        scanf("%lld%lld", &cut.day, &cut.limit);
        cut.start = get_cut_start(cut.day, cut.limit);
        ll harvest = 0;
        if (cut.start < n) {
            harvest = make_cut(cut);
        }
        printf("%lld\n", harvest);
    }
}

int main() {
    //int z; scanf("%d", &z); while(z--)
    one();
}