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

using namespace std;

struct tro{
    long long mi;
    long long kr;
    long long krn;
    int p;
    int k;
    void make(long long a, long long b, long long c, int d, int e)
    {
        mi=a;
        kr=b;
        krn=c;
        p=d;
        k=e;
    }
};

int n,m;
int tab[500007];
long long sp[500007];
stack<tro>S;

void wczytaj()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        scanf("%d",&tab[i]);
    sort(tab,tab+n+1);
    for(int i=1; i<=n+5; i++)
        sp[i]=sp[i-1]+tab[i];
    tro x;
    x.make(0,0,0,1,n);
    S.push(x);
}

long long suma(int a, int b)
{
    return sp[b]-sp[a-1];
}

int bin(int pp, int kk, long long mm, long long krr, long long bb)
{
    int pkp=pp;
    while(pp+1<kk)
    {
        int ss=(pp+kk)/2;
        if(mm+tab[ss]*krr>=bb)
            kk=ss;
        else
            pp=ss;
    }
    return kk;
}

void rob()
{
    long long ost=0;
    for(int te=0; te<m; te++)
    {
        long long wyn=0,d,b;
        scanf("%lld%lld",&d,&b);
        long long krog=d-ost;
        tro y, akt;
        y=S.top();
        int gdz=n+1;
        //printf("%lld %lld %lld %d %d\n",krog,y.mi,y.kr,y.p,y.k);
        if(!(y.mi+(y.kr+krog)*tab[y.k]<b))
        {
            ost=d;
            while(!S.empty()&&y.mi+(y.kr+krog)*tab[y.p]>=b)
            {
                y=S.top();
                akt=S.top();
                S.pop();
                wyn+=suma(y.p,y.k)*(y.kr+krog)+(y.mi-b)*(y.k-y.p+1);
                krog+=y.kr;
                gdz=y.p;
                if(!S.empty()) y=S.top();
            }
            if(S.empty())
            {
                akt.make(b,0,0,gdz,n);
                S.push(akt);
            }
            else
            {
                akt=S.top();
                S.pop();
                gdz=bin(akt.p,min(akt.k+2,n+1),akt.mi,krog+akt.kr,b);
                wyn+=suma(gdz,akt.k)*(akt.kr+krog)+(akt.mi-b)*(akt.k-gdz+1);
                y.make(akt.mi,akt.kr+krog,0,akt.p,gdz-1);
                S.push(y);
                y.make(b,0,0,gdz,n);
                S.push(y);
            }
        }
        printf("%lld\n",wyn);
    }
}

int main()
{
    wczytaj();
    rob();
    return 0;
}