/* Autor: Barbara Poszewiecka */
 

/* Nierekurencyjne drzewo przedzialowe, wykonujace w czasie O(log(n)) operacje:
 * 1. Dla wszystkich liczb z przedzialu [a,b] ustaw wartosc na
 *    f1(w_aktualna, w_nowa).
 * 2. Spytaj o f2 z wartosci liczb z przedzialu [a,b].
 * Zalozenie: f1, f2 kazda ze zbioru {max, +}.
 *
 * Zapożyczone z http://was.zaa.mimuw.edu.pl/sites/default/files/file/s2008-w02/koleje.cpp
 * Copyright doktor Kuba Radoszewski
 */

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

using namespace std;

long long max(long long x, long long y) {
  if (x > y) return x;
  return y;
}

/* Cztery makra parametryzujace zestaw operacji.
 * NIE dziala tylko f1=max, f2=+ */
#define f1(x, y) (x + y)
#define wiele(x, n) (x) /* f2(x,x,...,x) */
#define PUSTY 0 /* f2 od przedzialu bez wartosci */

#define MAX_N 500000
#define LOG_MAX_N 25 /* stala nieco wieksza od log(MAX_N) */

long long w[4 * MAX_N], W[4 * MAX_N]; /* wartosci w i W */
int n; /* Zakres wartosci punktow to: [0,n-1]. */
int ile; /* najmniejsza potega dwojki >=n */

/* [a,b] - przedzial, c - ustawiana wartosc */
inline void s_insert(int a, int b, long long c) {
  /* Operacje w lisciach. W przypadku niektorych kombinacji operacji
   * "if (a != b)" jest istotne, a dla innych nie szkodzi. */
  int va = ile + a, vb = ile + b;
  w[va] = f1(w[va], c);
  if (a != b) w[vb] = f1(w[vb], c);

  /* Spacer wskazniczkami va i vb do korzenia, polaczony z aktualizacjami
   * odpowiednich wartosci w i W. */
  int d = 0; /* odleglosc od najblizszego liscia (=wysokosc-glebokosc) */
  while (va != 1) {
    if (va / 2 != vb / 2) {
      if (va %2 == 0) w[va + 1] = f1(w[va + 1], c);
      if (vb %2 == 1) w[vb - 1] = f1(w[vb - 1], c);
    }
    va /= 2; vb /= 2;
    W[va] = max(f1(W[2 * va],wiele(w[2 * va], (1 << d))),
               f1(W[2 * va + 1],wiele(w[2 * va + 1], (1 << d))));
    W[vb] = max(f1(W[2 * vb],wiele(w[2 * vb], (1 << d))),
               f1(W[2 * vb + 1],wiele(w[2 * vb + 1], (1 << d))));
    d++;
  }
}


/* Makro pomocnicze do pierwszego spaceru do korzenia w zapytaniu. Jest ono
 * interesujace samo w sobie, gdyz l parametryzuje NAZWY zmiennych (dlatego
 * to musi byc makro, a nie np. funkcja). */
#define droga(l) do { \
  int w##l = 0, v##l = ile + l; \
  while (v##l != 0) { \
    pom##l[w##l++] = w[v##l]; \
    v##l /= 2; \
  } \
  for (int j = w##l - 2; j >= 0; j--) \
    pom##l[j] = f1(pom##l[j], pom##l[j + 1]); \
} while (0)

/* [a,b] - przedzial */
inline long long s_query(int a, int b) {
  /* W przypadku zapytania chec uzyskania nierekurencyjnej implementacji sporo
   * utrudnia. Wykonujemy przez to dwa przebiegi od lisci do korzenia.
   * W pierwszym wyznaczamy sumy czesciowe sumarycznych wkladow (tablice poma
   * i pomb) wartosci w na sciezkach od wezlow do korzenia do wyniku (sa to
   * albo maksima, albo sumy). */
  long long poma[LOG_MAX_N], pomb[LOG_MAX_N];
  droga(a); droga(b);
  int va = ile + a, vb = ile + b;

  /* W drugim przebiegu wyznaczamy wynik na podstawie wynikow dla przedzialow
   * bazowych z rozkladu [a,b]. */
  long long wynik = ((va != vb) ? max(poma[0], pomb[0]) : poma[0]);
  int d = 0; /* odleglosc od najblizszego liscia (=wysokosc-glebokosc) */
  while (va / 2 != vb / 2) {
    if (va % 2 == 0) wynik = max(wynik, f1(wiele(f1(poma[d + 1], w[va + 1]), (1 << d)), W[va + 1]));
    if (vb % 2 == 1) wynik = max(wynik, f1(wiele(f1(pomb[d + 1], w[vb - 1]), (1 << d)), W[vb - 1]));
    va /= 2; vb /= 2;
    d++;
  }
  return wynik;
}

void s_init() {
  ile = 2;
  while (ile < n) ile *= 2;
  for (int i = 1; i < 2*ile; i++) w[i] = W[i] = PUSTY;
}

int m; //liczba skoszeń trawy
vector<long long> pole;

vector<long long> kw_vec;
vector<long long> kw_wart_vec;

long long dl_trawy(int i) {
  vector<long long>::iterator up;
  
  up=std::upper_bound(kw_vec.begin(), kw_vec.end(), i);                   

  return s_query(i,i) * pole[i] + kw_wart_vec[(up- kw_vec.begin()) -1];
}

long long d_tab[MAX_N];
long long b_tab[MAX_N];

int find(long long x) {
    int l = 0;
    int p = n;
    int s;
    
    while (l < p) {
          s = (l + p) / 2;      
          if (x > dl_trawy(s)) l = s + 1; 
          else p = s;
    }
    
    return p;
}

long long pom[MAX_N + 5];

long long pomcos(int pocz, int kon){
    return pom[kon+1] - pom[pocz];
}


int main() { 

  scanf("%d %d", &n, &m);
  
  s_init();
  
  for (int i = 0; i < n ; i++) {
      int a;
      scanf("%d", &a);
      pole.push_back(a);
  }
    
  sort(pole.begin(), pole.end());

  pom[0] = 0LL;
  
  for (int i = 0; i < n ; i++) {
      pom[i+1] = pom[i] + pole[i];
  } 

  long long d0 = 0LL;
  
  for (int i = 0; i < m ; i++) {
      long long d, b;
      scanf("%lld %lld",&d, &b);
      
      d_tab[i] = d - d0;
      b_tab[i] = b;
      d0 = d;
  }
  
  kw_vec.push_back(0LL);
  kw_wart_vec.push_back(0LL);
 
  for (int i = 0; i < m ; i++) {
        
      s_insert(0, n - 1, d_tab[i]);
      
      long long x = b_tab[i];
      int s = find(x);
      
      if (dl_trawy(n - 1) <= x ) {
            cout << "0" << endl;
            continue;
      }       
      
      int ost = n - 1;
      long long kw;
      long long kw_wart; 
      
      long long suma = 0LL;
      
        
      while (!kw_vec.empty() &&  kw_vec.back() > s ) {
 
         kw = kw_vec.back();  
         kw_vec.pop_back();
         kw_wart = kw_wart_vec.back();
         kw_wart_vec.pop_back();

         suma +=  s_query(ost,ost) * pomcos(kw,ost)  +   (kw_wart - x) * (ost - kw + 1);

         s_insert(kw, ost,  - s_query(ost,ost));
         ost = kw - 1;
      }   

      suma += (kw_wart_vec.back() - x) * (ost - s + 1) +  s_query(ost,ost) * pomcos(s,ost) ;

      s_insert(s, ost,  - s_query(ost,ost));
     
      if ( s == kw_vec.back()) {
           kw_vec.pop_back();       
           kw_wart_vec.pop_back();  
     }
           
      kw_vec.push_back(s);
      kw_wart_vec.push_back(x); 
        
      cout << suma  << endl;
    
  } 
  
  return 0;
}