//Jakub Staro�
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <stdexcept>
#include <unordered_map>
#include <unordered_set>

#ifdef COMPILING_HOME
#define DEBUG_MODE
#endif

using namespace std;

typedef char int8;
typedef unsigned char uint8;
typedef short int int16;
typedef unsigned short int uint16;
typedef int int32;
typedef unsigned int uint32;
typedef long long int64;
typedef unsigned long long uint64;

typedef std::pair <int32, int32> int32_pair;
typedef std::pair <uint32, uint32> uint32_pair;
typedef std::pair <int64, int64> int64_pair;
typedef std::pair <uint64, uint64> uint64_pair;

typedef std::vector<bool> bit_vector;

#ifdef DEBUG_MODE
#define debug_print(x) cerr << #x << " = " << x << endl
#define print_line cerr << "Line " << __LINE__ << endl
#include <cassert>
#else
#define debug_print(x)
#define print_line
#define assert(x)
#endif

#define rep(i, x) for(int32 i = 0 ; i < (x) ; i++)
#define for_range(i, begin, end) for(auto i = (begin) ; i != (end) ; ++i )
#define all(c) (c).begin(),(c).end()
#define sort_all(x) sort( all(x) )
#define divide(a, b) ( ( (b)%(a) ) == 0 )
#define mp(x, y) make_pair(x,y)
#define pb(x) push_back(x)

#define sig(x) ( (x) == 0 ? 0 : ( (x) < 0 ? -1 : 1 ) )

const double epsilon = 1e-5;

template<class T>
void unique(std::vector <T> &v) {
  sort_all(v);
  v.resize(std::unique(all(v)) - v.begin());
}

ostream &newline(ostream &str) {
  str.put('\n');
  return str;
}

template<typename T1, typename T2>
istream &operator>>(istream &stream, std::pair <T1, T2> &pair) {
  stream >> pair.first >> pair.second;
  return stream;
}

template<typename T1, typename T2>
ostream &operator<<(ostream &stream, const std::pair <T1, T2> &pair) {
#ifdef DEBUG_MODE
  stream << "(" << pair.first << ", " << pair.second << ")";
#else
  stream << pair.first << ' ' << pair.second;
#endif
  return stream;
}

template<class T>
inline pair <T, T> operator+(const pair <T, T> &a, const pair <T, T> &b) {
  return pair<T, T>(a.first + b.first, a.second + b.second);
}

template<class T>
inline pair <T, T> operator-(const pair <T, T> &a, const pair <T, T> &b) {
  return pair<T, T>(a.first - b.first, a.second - b.second);
}

template<class T>
ostream &operator<<(ostream &str, const vector <T> &v) {
  if (!v.empty()) {
    for (int32 i = 0; i + 1 < v.size(); i++)
      str << v[i] << ' ';
    str << v.back();
  }
  return str;
}

struct koszenie_type {
  int64 time;
  int64 height;
  uint32 end_index;
};

ostream& operator<<(ostream& stream, const koszenie_type& koszenie) {
  stream << "(" << koszenie.time << ", " << koszenie.height << ", " << koszenie.end_index << ")";
  return stream;
}

class Application {
 public:
  Application() {
  }

  void Run() {
    WczytajDane();
    koszenie_type pierwotne_koszenie = {0, 0, N};
    koszenia.push_back(pierwotne_koszenie);
    rep(i, M) {
      int64 d, b;
      cin >> d >> b;
      koszenie_type koszenie;
      koszenie.time = d;
      koszenie.height = b;
      koszenie.end_index = N;
      int64 result = CutGrass(koszenie);
      cout << result << newline;
    }
  }

  int64 CutGrass(koszenie_type nowe_koszenie) {
    assert(!koszenia.empty());
    assert(koszenia[0].end_index == N);
    assert(koszenia.back().end_index > 0);
    uint32 cutting_end = find_cutting_end(nowe_koszenie);
    nowe_koszenie.end_index = cutting_end;

    int64 result = 0;

    uint32 begin = 0;
    uint32 end = min(koszenia.back().end_index, cutting_end);


    while (koszenia.back().end_index <= cutting_end) {

      result += delta_na_przedziale(begin, end, nowe_koszenie, koszenia.back());

      koszenia.pop_back();
      begin = end;
      end = min(koszenia.back().end_index, cutting_end);
    }

    result += delta_na_przedziale(begin, end, nowe_koszenie, koszenia.back());
    if (result > 0)
      koszenia.push_back(nowe_koszenie);
    return result;
  }

  int64 delta_na_przedziale(uint32 begin, uint32 end, const koszenie_type& nowe_koszenie, const koszenie_type& stare_koszenie) {
    int64 grass = grass_power_prefix[end] - grass_power_prefix[begin];
    int64 delta_t = nowe_koszenie.time - stare_koszenie.time;
    int64 delta_wysokosci = nowe_koszenie.height - stare_koszenie.height;
    int64 delta = delta_t * grass - (end - begin) * delta_wysokosci;
    return delta;
  }

  uint32 find_cutting_end(const koszenie_type& nowe_koszenie) {
    uint32 begin = 0;
    auto it = koszenia.rbegin();
    while (it != koszenia.rend() && majoryzuje_topowe_koszenie(nowe_koszenie, *it)) {
      begin = it->end_index;
      ++it;
    }

    uint32 end = (it == koszenia.rend())? N : it->end_index;

    if (it == koszenia.rend())
      assert(begin == end);

    while (begin < end) {
      uint32 middle = (begin + end) / 2;

      if (cos_zakosze(middle, nowe_koszenie, *it))
        begin = middle + 1;
      else
        end = middle;
    }
    return begin;
  }

  bool majoryzuje_topowe_koszenie(const koszenie_type& first, const koszenie_type& second) {
    return height_at(second.end_index - 1, first.time, second) > first.height;
  }

  int64 height_at(uint32 index, int64 current_time, const koszenie_type& last_koszenie) {
    return last_koszenie.height + grass_power[index] * (current_time - last_koszenie.time);
  }

  bool cos_zakosze(uint32 index, const koszenie_type& nowe, const koszenie_type& stare) {
    return height_at(index, nowe.time, stare) > nowe.height;
  }

  void WczytajDane() {
    cin >> N >> M;
    grass_power.resize(N);
    rep(i, N)
      cin >> grass_power[i];

    N++;
    grass_power.push_back(0);

    sort(all(grass_power), greater<uint64>());

    grass_power_prefix.assign(N + 1, 0);
    rep(i, N) {
      grass_power_prefix[i + 1] = grass_power_prefix[i] + grass_power[i];
    }
  }

  uint32 N, M;
  uint32 max_grass;
  vector<uint64> grass_power;
  vector<uint64> grass_power_prefix;

  vector<koszenie_type> koszenia;
};


int main() {
  ios::sync_with_stdio(0);
  Application application;
  application.Run();
  return 0;
}