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
115
// Artur Kraska, II UWr

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cmath>
#include <stack>
#include <list>
#include <set>
#include <map>

#define forr(i, n)                  for(int i=0; i<n; i++)
#define FOREACH(iter, coll)         for(typeof(coll.begin()) iter = coll.begin(); iter != coll.end(); ++iter)
#define FOREACHR(iter, coll)        for(typeof(coll.rbegin()) iter = coll.rbegin(); iter != coll.rend(); ++iter)
#define lbound(P,R,PRED)            ({typeof(P) X=P,RRR=(R), PPP = P; while(PPP<RRR) {X = (PPP+(RRR-PPP)/2); if(PRED) RRR = X; else PPP = X+1;} PPP;})
#define testy()                     int _tests; scanf("%d", &_tests); FOR(_test, 1, _tests)
#define CLEAR(tab)                  memset(tab, 0, sizeof(tab))
#define CONTAIN(el, coll)           (coll.find(el) != coll.end())
#define FOR(i, a, b)                for(int i=a; i<=b; i++)
#define FORD(i, a, b)               for(int i=a; i>=b; i--)
#define MP                          make_pair
#define PB                          push_back
#define deb(X)                      X;

#define M 1000000007
#define INF 1000000007

using namespace std;

#define suma(i, j) (sum[i] - sum[j+1])

int n, m;
long long d, b;
long long tab[1000007];
long long sum[1000007];

struct trawa
{
    long long poz;
    long long d;
    long long wys;
};
stack <trawa> stos;
trawa t;

int main()
{
    scanf("%d %d", &n, &m);
    forr(i, n)
    {
        scanf("%lld", &tab[i]);
    }
    sort(tab, tab+n);
    FORD(i, n-1, 0)
        sum[i] = sum[i+1] + tab[i];

    t.poz = t.d = t.wys = 0;
    stos.push(t);

    forr(i, m)
    {
        scanf("%lld %lld", &d, &b);

        long long last_poz = n;
        long long res = 0;

        while(!stos.empty())
        {
            t = stos.top();

            //cout << "  bada odcinek od " << t.poz << " do " << last_poz << ", d = " << t.d << ", wys = " << t.wys << endl;
            long long wys_poz = t.wys + (d - t.d)*tab[t.poz];
            if(wys_poz < b)
                break;

            stos.pop();
            res += suma(t.poz, last_poz-1)*(d - t.d) - (last_poz - t.poz)*(b-t.wys);
            //cout << "   wszedl caly, res = " << res << endl;
            last_poz = t.poz;
        }

        long long pocz = 0, kon, s;
        if(!stos.empty())
        {
            pocz = t.poz;
            kon = last_poz;
            while(pocz != kon)
            {
                s = (pocz + kon) >> 1;
                if(t.wys + tab[s]*(d - t.d) < b)
                    pocz = s+1;
                else
                    kon = s;
            }

            //cout << "  lb znalazl " << pocz << " do " << last_poz << ", d = " << t.d << ", wys = " << t.wys << endl;
            res += suma(pocz, last_poz-1)*(d - t.d) - (last_poz - pocz)*(b-t.wys);
        }

        if(pocz < n)
        {
            t.d = d;
            t.wys = b;
            t.poz = pocz;
            stos.push(t);
        }

        printf("%lld\n", res);
    }

    return 0;
}