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

//#define DBG
//#define TEST

using namespace std;

struct Koszenie {
  long long d;  // numer dnia
  long long b;  // wysokość koszenia
  int c;  // ostatni numer skoszonej trawy (najwolniejsza trawa skoszona w tym koszeniu)
};

bool cmp(int a, int b) {return a > b;}

int n, m, *a;
long long *b, *d;


/////////////////////////////////////////////////////////////////////////////////////////////

void licz(long long *twyn)
{
  int i;
  long long *sa = new long long[n + 1];  //sa[i] = sum(a[0]..a[i-1])
                                         //sa[j + 1] - sa[i] = sum(a[i]..a[j]) dla j >= i
  #define SUMA(i, j) (sa[j + 1] - sa[i])
  #define ILE(i, j)  (j - i + 1)

  sort(a, a + n, cmp);  // sortowanie traw malejąco
  sa[0] = 0;
  for (i = 0; i < n; ++i) sa[i + 1] = sa[i] + a[i];

  Koszenie *K = new Koszenie[m];  // K[i] dane kolejnego koszenia wg rosnącego c i d
  int ik = -1; // ostatni element wypełniony w K

  for (i = 0; i < m; ++i) {
    #ifdef DBG
    printf("i=%d\n", i);
    #endif
    long long wyn = 0;
    int c0 = 0; // najszybsza trawa która jest w analizowanym fragmencie
    // jeśli cięcie jest poniżej lub równo wysokości do której urosła najwolniejsza trawa skoszona w danym koszeniu
    // od tamtego dnia to cały fragment jest równo cięty, a punkt graniczny będzie gdzieś dalej
    // albo dokładnie na granicy jak kolejna jest już za niska do cięcia

    while (ik >= 0 && b[i] <= K[ik].b + (d[i] - K[ik].d) * a[K[ik].c]) {
      #ifdef DBG
      long long tmp = SUMA(c0, K[ik].c) * (d[i] - K[ik].d) - ILE(c0, K[ik].c) * (b[i] - K[ik].b);
      printf("   %I64d * (%I64d - %I64d) - %d * (%I64d - %I64d) = %I64d\n",
             SUMA(c0, K[ik].c), d[i], K[ik].d, ILE(c0, K[ik].c), b[i], K[ik].b, tmp);
      wyn += tmp;
      printf("   fragment ik=%d, c0=%d, K[ik].c=%d siano=%I64d wyn=%I64d\n", ik, c0, K[ik].c, tmp, wyn);
      #else

      wyn += SUMA(c0, K[ik].c) * (d[i] - K[ik].d) // wszystko co urosło w tym segmencie od ostatniego koszenia
          -  ILE(c0, K[ik].c) * (b[i] - K[ik].b); // ile zostaje bo tniemy wyżej niż poprzednio
      #endif
      c0 = K[ik].c + 1;
      ik--;
    }
    // UWAGA: co jeśli cięcie było na najwolniejszej trawie?   --> patrz (**)
    // UWAGA: co jeśli nic się nie zetnie bo cięcie za wysoko? będzie dobrze bo znajdzie się skrajny lewy i warunek
    //        sprawdzi, że nie ciąć (ale możnaby to if-em normalnym obsłużyć bez tego b-searcha)


    // znaleźć c = miejsce cięcia w znalezionym fragmencie c0..c1
    int c1; // najwolniejsza trawa w fragmencie, o której wiadomo, że żadna wolniejsza nie jest cięta
    long long b1; // wysokość ostatniego cięcia trawy c1
    long long d1; // dzień ostatniego cięcia trawy c1

    if (ik == -1) { // trzeba sprawdzić fragment do końca - przypadek, że najwolniejsza trawa nigdy nie była cięta (**)
      c1 = n - 1;
      b1 = 0;
      d1 = 0;
    }
    else {
      c1 = K[ik].c;
      b1 = K[ik].b; // wysokość ostatniego cięcia najwolniejszej trawy we fragmencie
      d1 = K[ik].d;
    }

    #ifdef DBG
    printf("   ik=%d, c0=%d, c1=%d, b1=%I64d, d1=%I64d, wyn=%I64d\n", ik, c0, c1, b1, d1, wyn);
    #endif

    // wysokość trawy c (=c0..c1) to b1 + (d - d1) * a[c]
    // trzeba znaleźć największe c, t.że b1 + (d - d1) * a[c] >= b
    int c;
    int lewy = c0, prawy = c1;
    while (prawy > lewy) {
      int srodek = (lewy + prawy + 1) / 2;
      if (b1 + (d[i] - d1) * a[srodek] >= b[i])
        lewy = srodek;
      else
        prawy = srodek - 1;
    }
    #ifdef DBG
    printf("   lewy=%d, prawy=%d\n", lewy, prawy);
    #endif
    c = lewy;

    if (c0 <= c1 && // jeśli statnie cięcie w pętli było do najwolniejszej trawy to tu już nie ma co ciąć
        b1 + (d[i] - d1) * a[c] >= b[i]) {
      #ifdef DBG
      long long tmp = SUMA(c0, c) * (d[i] - d1)  // wszystko co urosło od ostatniego koszenia
          -  ILE(c0, c) * (b[i] - b1);  // ile zostaje bo tniemy wyżej niż poprzednio
      printf("   tniemy reszte do %d siano=%I64d\n", c, tmp);
      #endif

      // było cięcie - doliczyć ilość ściętej trawy od c0 do c
      wyn += SUMA(c0, c) * (d[i] - d1)  // wszystko co urosło od ostatniego koszenia
          -  ILE(c0, c) * (b[i] - b1);  // ile zostaje bo tniemy wyżej niż poprzednio

      ik++;     // odłożyć ostatnie cięcie na K
      K[ik].d = d[i];
      K[ik].b = b[i];
      K[ik].c = c;
    }
    else {
      if (c0 > 0) {
        // było cięcie w pętli - trzeba je odłożyć do K skoro nie było potem cięcia w środku fragmentu lub na końcu
        ik++;
        K[ik].d = d[i];
        K[ik].b = b[i];
        K[ik].c = c0 - 1;
      }
    }
    #ifdef DBG
    for(int q = 0; q <= ik; ++q) printf("     %d (c=%d, d=%I64d, b=%I64d)\n", q, K[q].c, K[q].d, K[q].b);
    printf("   teraz jest=%I64d\n", wyn);
    #endif

    twyn[i] = wyn;
  }
  delete K;
}

#ifdef TEST
#include "sia_test.h"
#endif // TEST

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

#ifdef TEST
  test();
  return 0;
#endif // TEST

  int i = 0;
  scanf("%d%d", &n, &m);
  a = new int[n];
  b = new long long[m];
  d = new long long[m];
  long long *wyn = new long long[m];
  for (i = 0; i < n; ++i) scanf("%d", a + i);
  for (i = 0; i < m; ++i) scanf("%lld%lld", d + i, b + i);
  licz(wyn);
  for (i = 0; i < m; ++i) printf("%lld\n", wyn[i]);


  return 0;
}