1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <cstdio>
#include <algorithm>

using std::printf;
using std::scanf;
using std::sort;
using std::upper_bound;
using std::lower_bound;

struct Interval
{
  long long day;
  int fromId;
  int toId;
  long long height;
};

long long growths[500001];
long long cummulatedGrowths[500001];
Interval intervals[500001];
int intervalsLength;
int n, m;
long long d, h;

int intervalsLower(const int, const Interval & interval)
{
  long long days = d - interval.day;
  long long endHeight = interval.height + days * growths[interval.toId - 1];
  return h <= endHeight ? 1 : 0;
}

long long countWeight(int fromIndex, int toIndex, const Interval * interval)
{
  long long days = d - interval->day;
  int count = toIndex - fromIndex;
  return (cummulatedGrowths[fromIndex] - cummulatedGrowths[toIndex]) * days + (interval->height - h) * count;
}

int main()
{
  scanf("%d%d", &n, &m);
  
  for (int i = 0; i < n; i++)
    scanf("%lld", growths + i);
  sort(growths, growths + n);
  cummulatedGrowths[n] = 0;
  for (int i = n - 1; i >= 0; i--)
    cummulatedGrowths[i] = growths[i] + cummulatedGrowths[i + 1];

  intervals[0].day = 0;
  intervals[0].fromId = 0;
  intervals[0].toId = n;
  intervals[0].height = 0;
  intervalsLength = 1;

  for (int di = 0; di < m; di++)
  {
    scanf("%lld%lld", &d, &h);

    Interval * foundPtr = upper_bound(intervals, intervals + intervalsLength, 0, intervalsLower);
    int foundIndex = foundPtr - intervals;
    if (foundIndex == intervalsLength)
    {
      printf("0\n");
      continue;
    }
    //foundPtr->height + (d - foundPtr->day) * x >= h
    long long searchedHeight = (h - foundPtr->height) / (d - foundPtr->day);
    if ((h - foundPtr->height) % (d - foundPtr->day) > 0)
      searchedHeight++;
    long long * foundGrowth = lower_bound(growths + foundPtr->fromId, growths + foundPtr->toId, searchedHeight);
    int foundGrowthIndex = foundGrowth - growths;

    long long weightSum = 0;
    weightSum += countWeight(foundGrowthIndex, foundPtr->toId, foundPtr);
    for (int ii = foundIndex + 1; ii < intervalsLength; ii++)
      weightSum += countWeight(intervals[ii].fromId, intervals[ii].toId, intervals + ii);

    printf("%lld\n", weightSum);

    if (foundGrowthIndex == foundPtr->fromId)
    {
      foundPtr->day = d;
      foundPtr->height = h;
      foundPtr->toId = n;
      intervalsLength = foundIndex + 1;
    }
    else
    {
      foundPtr->toId = foundGrowthIndex;
      Interval * nextPtr = foundPtr + 1;
      nextPtr->day = d;
      nextPtr->height = h;
      nextPtr->fromId = foundGrowthIndex;
      nextPtr->toId = n;
      intervalsLength = foundIndex + 2;
    }
  }

  return 0;
}