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
program sia;

type
  tab = array[0..500000] of longword;

var
  n: longword;
  m: longword;
  a: array[0..500000] of longword;

  b: array[1..500000] of Qword;
  d: array[1..500000] of Qword;

  S: Qword;
  S0: Qword;
  h0: Qword;

  i,j: longword;

procedure qsort(var t:tab; l,r:longword);
var
  p,tmp: longword;
  i,j: longword;
  begin
    i:=l; j:=r;
    tmp:=(l+r) div 2;
    p:=t[tmp];
    repeat
      while t[i]<p do i:=i+1;
      while p<t[j] do j:=j-1;
      if i<=j then
      begin
        tmp:=t[i]; t[i]:=t[j]; t[j]:=tmp;
        tmp:=t[i]; t[i]:=t[j]; t[j]:=tmp;
        tmp:=t[i]; t[i]:=t[j]; t[j]:=tmp;
        i:=i+1; j:=j-1
      end
    until i>=j;
    if l<j then qsort(t,l,j);
    if i<r then qsort(t,i,r)
  end;

begin
  readln(n,m);
  for i:=1 to n do
    read(a[i]);
  readln();
  for i:=1 to m do
    readln(d[i],b[i]);
  qsort(a,1,n);

  for i:=1 to m do
  begin
    S:=0;
    h0:=b[i] div d[i];
    j:=n;
    while a[j]>h0 do
    begin
      S:=S+a[j];
      j:=j-1
    end;
    if j=n then writeln('0')
    else
    begin
      S:=S*d[i]-b[i]*(n-j);
      if S<=S0 then writeln('0')
      else
      begin
        writeln(S-S0);
        S0:=S
      end
    end;
  end;
end.