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
// sia.cpp : Defines the entry point for the console application.
//



#include "stdio.h"

#define	NN	500000L
#define	MM	500000L

struct	kkk	{
				long long	 d;
				long long	 h;
			} kk[MM+1];

long		 vv[NN];
long long	 hh[NN];
long long	 w, d, h, t;

long		 n, m, i, j;


int main()
{
	scanf("%ld %ld", &n, &m);

	for (i=0; i<n; i++)
		scanf("%ld", &vv[i]);

	for (j=1; j<=m; j++)
		scanf("%ld %lld", &kk[j].d, &kk[j].h);

	for (j=1; j<=m; j++)
	{
		w	= 0;
		d	= kk[j].d - kk[j-1].d;
		h	= kk[j].h;
		for (i=0; i<n; i++)
		{
			t	= hh[i] + d * vv[i];
			if (t>h)
			{
				w	+= t - h;
				t	 = h;
			}
			hh[i]	= t;
		}
		printf("%lld\n", w);
	}

	return 0;
}