siano

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdint>
#include <stack>

using namespace std;


struct ciecie
{public:
    int64_t d,b;
    ciecie() : d(0),b(0){};
    ciecie (int64_t d_, int64_t b_) : d(d_),b(b_){};
};

struct koszenie
{
    ciecie ciach;
    int index;
    koszenie (int64_t d_, int64_t b_, int index_): ciach{d_,b_},index(index_) {};
    koszenie (ciecie ciach_, int index_): ciach{ciach_},index(index_) {};
};

vector<int64_t> a;
vector<int64_t> cumsum;

int64_t wysokosc ( const koszenie &kosz, const int64_t czas )
{
    return (czas-kosz.ciach.d)*a[kosz.index] + kosz.ciach.b;
}

int main()
{
    ios_base::sync_with_stdio(false);

    int m,n;
    cin>>n>>m;

    a=vector<int64_t>(n,0);
    cumsum = vector<int64_t>(n+1,0);


    for (int i=0;i<n;i++)
         cin>>a[i];

    sort(begin(a),end(a));

    for (int i=n-1;i>=0 ;i--)
        cumsum[i]=a[i]+cumsum[i+1];

    vector<ciecie> cuts(m);

    for (int i=0;i<m;i++)
    {
         cin>>cuts[i].d;
         cin>>cuts[i].b;
    }

    stack <koszenie> koszenia;

    koszenia.push( koszenie{0,0,0} );

    for (vector<ciecie>::iterator itcut = begin(cuts); itcut !=end(cuts); ++itcut )
    {
        int i, last_i=n;
        int64_t t = itcut->d;
        int64_t c = itcut->b;
        int64_t skoszono =0;
        while (!koszenia.empty() && wysokosc(koszenia.top(),t)> c )
        {
            koszenie kosz = koszenia.top();
            i=kosz.index;
            skoszono += (kosz.ciach.b-c)*(last_i-i) + (cumsum[i]-cumsum[last_i])*(t-kosz.ciach.d);

            koszenia.pop();
            last_i = i;
        }

        if (!koszenia.empty())
        {
            //wysokosc[i] = a[i]*(t-d) + b > c
            //pstatni, ktory nie zostanie skoszony
            //a[i]*(t-d) + b  = c
            //a[i] = ((c - b) / (t-d) )
            koszenie kosz = koszenia.top();
            int64_t  a_cel= (c  - kosz.ciach.b )/(t-kosz.ciach.d); //najwiekszy przyrost, który nie da skoszenia.
            auto it_a = upper_bound( begin(a)+kosz.index , begin(a)+last_i, a_cel );
            i = it_a-begin(a);

            skoszono += (cumsum[i]-cumsum[last_i])*(t-kosz.ciach.d) +(kosz.ciach.b-c)*(last_i-i);
        }
        if (skoszono>0)
            koszenia.push( koszenie{*itcut,i} );
        cout<<skoszono<<endl;

    }
    return 0;
}