#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>

using namespace std;

typedef vector<int> VI;
typedef long long LL;

#define FOR(x, b, e) for(int x = b; x <= (e); ++x)
#define FORD(x, b, e) for(int x = b; x >= (e); --x)
#define REP(x, n) for(int x = 0; x < (n); ++x)
#define VAR(v, n) __typeof(n) v = (n)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(x) ((int)(x).size())
#define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define PB push_back
#define ST first
#define ND second
#define MP make_pair

typedef pair<int,int> para;

struct cut {
  LL day;
  LL h;
  LL sum;
  int fst;
  int ile;
  int a0;
};

//inline LL h(LL b)



int main() {
  int n, m, p;
  LL s, d, b;
	VI a;
	vector<LL> sum;
	cut c;
	stack<cut> st;

	scanf("%d%d",&n,&m);
	a.reserve(n+1);
  sum.reserve(n+1);

  REP(i,n) {
    scanf("%d",&p);
    a.PB(p);
  }

  a.PB(0);                           //n++;
  sort(ALL(a),greater<int>());

  s=0;
  FORD(i,n,0){
    s+=a[i];
//cout<<"s[i]
    sum.PB(s);
  }

  reverse(ALL(sum));

  c.day=0;
  c.h=0;
  c.sum=0;
  c.fst=n;
  c.ile=1;
  c.a0=0;
  st.push(c);

  c.day=0;
  c.h=1;
  c.sum=sum[0];
  c.fst=0;
  c.ile=n;
  c.a0=a[n-1];
  st.push(c);


  REP(j,m) {
    scanf("%lld%lld",&d,&b);
    b++;
    s=0;
    c=st.top();

    while (c.h+c.a0*(d-c.day)>=b) {
      s+=(c.h-b)*c.ile+c.sum*(d-c.day);
      st.pop();
      c=st.top();
    }

    if (c.h+a[c.fst]*(d-c.day)<=b) {
      p=c.fst;
      c.day=d;
      c.h=b;
      c.sum=sum[0]-sum[p];
      c.fst=0;
      c.ile=p;
      c.a0=a[p-1];
      st.push(c);
      printf("%lld\n",s);
      continue;
    }

    st.pop();

    int i, ile, f0, fst, nxt, step;
    LL dh, dt;
    ile=c.ile;
    f0=fst=c.fst;
    dh=b-c.h;
    dt=d-c.day;

    while (ile>0) {
      i=fst; step=ile/2; i+=step;
      if (a[i]*dt>=dh) {fst=++i; ile-=step+1;}          //i do ciêcia
      else ile=step;
    }                      //return fst

//  c.day= ;   bez zmian
//  c.h= ;            "
  nxt=st.top().fst;
  c.sum=sum[fst]-sum[nxt];
  c.fst=fst;
  c.ile=nxt-fst;
  c.a0=a[nxt-1];
  st.push(c);



  c.day=d;
  c.h=b;
  c.sum=sum[0]-sum[fst];
  c.fst=0;
  c.ile=fst;
  c.a0=a[fst-1];
  st.push(c);

  s+=c.sum*dt-dh*fst;
//s+=(c.h-b)*c.ile+c.sum*(d-c.day);
  printf("%lld\n",s);

  }
  return 0;
}