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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.LinkedList;
import java.util.List;

public class sia {
	private static class frac {
		long licznik;

		long mianownik;

		frac(long l, long m) {
			licznik = l;
			mianownik = m;
		}

		public void add(frac f) {
			licznik = licznik * f.mianownik + mianownik * f.licznik;

			mianownik *= f.mianownik;
		}

		public void multiply(frac f) {
			licznik *= f.licznik;

			mianownik *= f.mianownik;
		}

		public void sub(frac f) {
			f.licznik = -f.licznik;
			add(f);
		}

		public void div(frac f) {
			long tmp = f.licznik;
			f.licznik = f.mianownik;
			f.mianownik = tmp;
			multiply(f);
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer st = new StreamTokenizer(bufferedReader);
		try {
			st.nextToken();
			int n = (int) st.nval;
			st.nextToken();
			int m = (int) st.nval;

			// long sum = 0;
			long[] raises = new long[n];
			long[] heights = new long[n];
			for (int i = 0; i < n; i++) {
				st.nextToken();
				// sum += (long) st.nval;
				raises[i] = (long) st.nval;
				heights[i] = raises[i];
			}

			// frac raisingAve = new frac(sum, n);
			List<Long> results = new LinkedList<Long>();
			
			long d, b = 0;
			long last  = 1;
			long helper = 0;
			for (int i = 1; i <= m; i++) {
				st.nextToken();
				d = (long) st.nval;
				st.nextToken();
				b = (long) st.nval;
				long res = 0;	
				
				for (int j = 0; j < n; j++) {
					helper = (d - last) * raises[j] + heights[j];
					res += Math.max(0, helper - b);
					heights[j] = Math.min(helper, b);					
				}
				last = d;
				results.add(res);

			}

			bufferedReader.close();

			results.forEach(System.out::println);

		} catch (Exception e) {

		}

	}
}