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
116
117
118
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

const int inf = 2020020;
const int N = 500005;
int A[N];
long long B[N][3];
long long PS[N];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i) scanf("%d",&A[i]);
    sort(A,A+n);
    PS[0]=A[0];
    for(int i=1;i<n;++i)
        PS[i]=PS[i-1]+A[i];

    long long x,y;
    B[0][0]=B[0][1]=B[0][2]=0;

    int gw=0;
    for(int i=0;i<m;++i) {
        scanf("%lld%lld",&x,&y);

        if (B[gw][1]+A[n-1]*(x-B[gw][0])<=y)
        {
            printf("0\n");
            continue;
        }

        int w=gw;
        int p1,p2;
        while(w>0) {
            if (B[w][1]+(x-B[w][0])*A[B[w][2]]>y)
                --w;
            else break;
        }
        if (gw>w) {
            if (B[w][1]+(x-B[w][0])*A[B[w+1][2]-1]<=y)
                ++w;
            p1=B[w][2];
            p2 = (w==gw) ? n-1 : B[w+1][2]-1;

        }
        else {
            p1=B[w][2];p2=n-1;
        }
        //cout << p1 << " " << p2 << endl;
        int md;
        while(p2>p1) {
            md = (p2+p1)/2;
            if (A[md]*(x-B[w][0])+B[w][1]>y)
                p2=md;
            else p1=md+1;
        }
        md=p2;

        //cout << md << " " << w << " " << gw<< endl;
        long long ret=-(n-md)*y;

        if (B[gw][2]<=md) {
            ret += (PS[n-1]-PS[md-1])*(x-B[gw][0])+(n-md)*(B[gw][1]);

            if (B[gw][2]!=md) ++gw;
            B[gw][0]=x;
            B[gw][1]=y;
            B[gw][2]=md;

            printf("%lld\n",ret);
            continue;
        } else {
            int gw2 = gw;
            if (B[gw][2]>0)
                ret += (PS[n-1]-PS[B[gw][2]-1])*(x-B[gw][0])+(n-B[gw][2])*B[gw][1];
            else
                ret += (PS[n-1]-0)*(x-B[gw][0])+(n-0)*B[gw][1];

            while(gw>0 && B[gw-1][2]>=md) {
                ret += (PS[B[gw][2]-1]-PS[B[gw-1][2]-1])*(x-B[gw-1][0])+(B[gw][2]-B[gw-1][2])*B[gw-1][1];
                --gw;
            }

            if (gw2==0) {
                if (md>0)
                    ret += (PS[B[0][2]-1] - PS[md-1])*(x);
                else
                    ret += (PS[B[0][2]-1] - 0)*x;
                gw=0;
            } else {
                if (gw==0) {
                    if (md<B[0][2]) {
                        if (md>0) {
                            ret+=(PS[B[0][2]-1]-PS[md-1])*(x);
                        } else {
                            ret+=(PS[B[0][2]-1]-0)*(x);
                        }
                    }
                } else {
                    ret += (PS[B[gw][2]-1]-PS[md-1])*(x-B[gw-1][0])+(B[gw][2]-md)*B[gw-1][1];
                }
            }
            B[gw][0]=x;
            B[gw][1]=y;
            B[gw][2]=md;

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

    return 0;
}