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
#include <cstdio>
#include <utility>
#include <algorithm>
#include <vector>
using namespace std;
long long tree[1100000];
vector < pair < long long, long long> > stos;
long long n, m, a[500001], treesize = 1, pom;
long long d[500001], b[500001], suf[500002], pom2, h, t, wyn, pom3;
long long query(int a) {
    long long va = a + treesize - 1, ret = 0;
    while (va != 0) {
        if (tree[va] > ret)
            ret = tree[va];
        va /= 2;
    }
    return ret;
}
void ins(int a, int b) {
    long long va = a + treesize - 1;
    tree[va] = b;
    while (va != 0) {
        if (va % 2 == 0)
            tree[va+1] = b;
        va /= 2;
    }
    return;
}
long long binser() {
long long l = 1, p = n, sr, ret = n+1, pom;
while (l <= p) {
    sr = (l+p)/2;
    pom = query(sr);
    pom = (t-d[pom])*a[sr]+b[pom];
    if (pom <= h)
       l = sr+1;
    else {
        p = sr-1;
        ret = sr;
    }
}
return ret;
}
int main() {
    scanf("%lld%lld", &n, &m);
    while(treesize < n)
        treesize *= 2;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    sort(a+1, a + n + 1);
    for (int i = n; i >= 1; i--)
        suf[i] = a[i] + suf[i+1];
    stos.push_back(make_pair(0,0));
    for (int i = 1; i <= m; i++) {
        wyn = 0;
        scanf("%lld%lld", &d[i], &b[i]);
        t = d[i];
        h = b[i];
        pom = binser();
      //  printf("%d\n", pom);
        ins(pom, i);
        pom3 = n+1;
        while(stos[stos.size()-1].first >= pom) {
            wyn += (suf[stos[stos.size()-1].first] - suf[pom3])*(t-d[stos[stos.size()-1].second])-(pom3-stos[stos.size()-1].first)*(h-b[stos[stos.size()-1].second]);
            pom3 = stos[stos.size()-1].first;
            stos.pop_back();
        }
        wyn += (suf[pom] - suf[pom3])*(t-d[stos[stos.size()-1].second])-(pom3-pom)*(h-b[stos[stos.size()-1].second]);
        stos.push_back(make_pair(pom,i));
        printf("%lld\n", wyn);
        }
    return 0;
}