#include<bits/stdc++.h>
#define lc(p) 2*p
#define rc(p) 2*p+1
using namespace std;
const int maxn = 5e5 + 10;
int n, m;

long long day[maxn], b[maxn];
long long a[maxn];
long long seth[maxn << 2]; //标记，代表要赋的高度
long long setd[maxn << 2];
struct node {
    long long minh, sumh, sumv, maxh;
} d[maxn << 2];//维护第i次割完的高度
void update(int p) {
    d[p].sumh = d[lc(p)].sumh + d[rc(p)].sumh;
    d[p].sumv = d[lc(p)].sumv + d[rc(p)].sumv;
    d[p].minh = d[lc(p)].minh;
    d[p].maxh = d[rc(p)].maxh;
}
void xf(int l, int r, int p, long long sd, long long sh) {
    int m = l + ((r - l) >> 1);
    if (sh != -1) {//区间赋值
        d[lc(p)].sumh = (m - l + 1) * sh;
        d[rc(p)].sumh = (r - m) * sh;
        d[lc(p)].minh = d[lc(p)].maxh = d[rc(p)].minh = d[rc(p)].maxh = sh;
        
		seth[lc(p)] = seth[rc(p)] = sh;
        setd[lc(p)] = setd[rc(p)] = 0;
        seth[p] = -1;
    }
    if (sd != 0) {//区间加法
        d[lc(p)].sumh += sd * d[lc(p)].sumv;
        d[lc(p)].minh += sd * a[l];
        d[lc(p)].maxh += sd * a[m];
        setd[lc(p)] += sd;

        d[rc(p)].sumh += sd * d[rc(p)].sumv;
        d[rc(p)].minh += sd * a[m + 1];
        d[rc(p)].maxh += sd * a[r];
        setd[rc(p)] += sd;

        setd[p] = 0;
    }
    return;
}
void build(int s, int t, int p) {
    if (s == t) {
        d[p].maxh = d[p].minh = 0;
        d[p].sumh = 0;
        d[p].sumv = a[s];
        seth[p] = -1;
        setd[p] = 0;

        return;
    }
    int m = s + ((t - s) >> 1);
    build(s, m, lc(p));
    build(m + 1, t, rc(p));
    update(p);
    seth[p] = -1;
    setd[p] = 0;

    return;
}
long long getsum(int s, int t, int p, int i) {//区间赋值
    if (d[p].minh >= b[i]) {
        long long re = d[p].sumh - (t - s + 1) * (b[i]);
        d[p].sumh = (t - s + 1) * b[i];
        d[p].minh = b[i];
        d[p].maxh = b[i];
        seth[p] = b[i];
        setd[p] = 0;
//        cout << p << " " << d[p].sumh << " " << d[p].sumv << " " << d[p].minh << " " << d[p].maxh << endl;
        return re;
    }
    xf(s, t, p, setd[p], seth[p]);
    int m = s + ((t - s) >> 1);
    long long re = 0;
    if (d[lc(p)].maxh >= b[i])
        re += getsum(s, m, lc(p), i);
    if (d[rc(p)].maxh >= b[i])
        re += getsum(m + 1, t, rc(p), i);
    update(p);
//    cout << p << " " << d[p].sumh << " " << d[p].sumv << " " << d[p].minh << " " << d[p].maxh << endl;
    return re;
}
void change(int l, int r, long long sd, int s, int t, int p) {//区间加法
    if (l <= s && t <= r) {
        d[p].minh += a[s] * sd;
        d[p].maxh += a[t] * sd;
        d[p].sumh += d[p].sumv * sd;
        setd[p] += sd;

        return;
    }
    
    int m = s + ((t - s) >> 1);
    xf(s, t, p, setd[p], seth[p]);
    
    if (l <= m)change(l, r, sd, s, m, lc(p));
    if (r > m)change(l, r, sd, m + 1, t, rc(p));
    update(p);
    return;
}
int main() {
  	freopen("in.in", "r", stdin);
  	freopen("out.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    for (int i = 1; i <= m; i++) {
        scanf("%lld%lld", &day[i], &b[i]);
    }
    sort(1 + a, 1 + a + n);
    build(1, n, 1);
    for (int i = 1; i <= m; i++) {
        long long d = day[i] - day[i - 1];
        change(1, n, d, 1, n, 1);
        cout << getsum(1, n, 1, i) << endl;
    }
    return 0;
}