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

using namespace std;

struct mow
{
    mow(int p_start, long long p_d, long long p_b) { start = p_start; d = p_d; b = p_b; }
    int start;
    long long d;
    long long b;
};

long long d_diff, old_b;

bool lower(int a, long long b)
{
    return (old_b + a*d_diff < b);
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
        
    sort(a.begin(), a.end());
    
    vector<long long> a_sum(n+1);
    a_sum[n] = 0;
    for (int i = n-1; i >= 0; i--)
        a_sum[i] = a[i] + a_sum[i+1];
    
    stack<mow> stk;
    
    for (int i = 0; i < m; i++)
    {
        long long d, b;
        scanf("%lld %lld", &d, &b);
        
        int last = n;
        long long sum = 0;
        while (!stk.empty())
        {
            long long height = stk.top().b + a[stk.top().start]*(d-stk.top().d);
            if (height < b)
                break;
            sum += (a_sum[stk.top().start]-a_sum[last]) * (d-stk.top().d)
                    + (stk.top().b - b) * (last-stk.top().start);
            
            last = stk.top().start;
            stk.pop();
        }
        
        d_diff = d - (stk.empty() ? 0 : stk.top().d);
        old_b = (stk.empty() ? 0 : stk.top().b);
        int first = (stk.empty() ? 0 : stk.top().start+1);
        if (first < last)
        {
            first = lower_bound(a.begin()+first, a.begin()+last, b, lower) - a.begin();
            if (first < last)
            {
                sum += (a_sum[first]-a_sum[last]) * (d_diff)
                    + (old_b - b) * (last-first);
            }
        }
        if (first < n)
            stk.push(mow(first, d, b));
            
        printf("%lld\n", sum);
    }
    

    // system("pause");
        
    return 0;
}