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
#include <stdio.h>
#include <stdlib.h>
#define MAX(X, Y) (((X) >= (Y)) ? (X) : (Y))
#define MIN(X, Y) (((X) <= (Y)) ? (X) : (Y))

int main(void) {
  int i, j, n, m, *a;
  long long ds,s=0,d=0,dn,b,*st;

  scanf("%d%d",&n,&m);
  a = (int *)malloc(n*sizeof(int));
  st = (long long*)malloc(n*sizeof(long long));


  for (i=0;i<n;++i) {
    scanf("%d",&a[i]);
    st[i]=0;
  }

  for (i=0;i<m;++i) {
    scanf("%lld%lld",&dn,&b);
    for (j=0;j<n;++j) {
      ds=(dn-d)*a[j]+st[j];
      s+=MAX(ds-b,0);
      st[j]=MIN(ds,b);
    }
    /*                                                                                                                                                                                                                                                                         
    for (j=0;j<n;++j) {                                                                                                                                                                                                                                                        
      printf(" %lld",st[j]);                                                                                                                                                                                                                                                   
      } printf("\n");*/
    printf("%lld\n",s);
    d=dn;s=0;
  }

  /*                                                                                                                                                                                                                                                                           
  printf("%d %d\n",n,m);                                                                                                                                                                                                                                                       
  for (i=0;i<n;++i) {                                                                                                                                                                                                                                                          
    printf(" %d",a[i]);                                                                                                                                                                                                                                                        
  }                                                                                                                                                                                                                                                                            
  printf("\n");                                                                                                                                                                                                                                                                
  */

  free(a);
  free(st);
  return 0;
}