import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, core.stdc.stdio; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto A = readln.split.map!(to!long).array; auto XW = iota(M).map!(_ => readln.split.map!(to!int).array).array; auto B = new long[](N); foreach (xw; XW) B[xw[0]-1] += xw[1]; if (N.iota.map!(i => A[i] <= B[i]).any) { writeln(-1); return; } long[] calc(int[] X, long[] Y) { auto LtoR = new long[](N); auto RtoL = new long[](N); foreach (i; 0..M) { auto idx = X[i]; if (idx < N - 1) LtoR[idx+1] += Y[i]; if (idx > 0) RtoL[idx-1] += Y[i]; } foreach (i; 0..N-1) LtoR[i+1] += LtoR[i]; foreach (i; 0..N-1) LtoR[i+1] += LtoR[i]; foreach_reverse (i; 1..N) RtoL[i-1] += RtoL[i]; foreach_reverse (i; 1..N) RtoL[i-1] += RtoL[i]; return N.iota.map!(i => LtoR[i] + RtoL[i]).array; } auto X = XW.map!(xw => xw[0].to!int-1).array; auto Y1 = new long[](M); Y1[] = 1; auto Y2 = XW.map!(xw => xw[1].to!long).array; auto C = calc(X, Y1); auto D = calc(X, Y2); auto S = Y2.sum; auto ans = 0L; foreach (i, a; A) if (a <= S) { ans = max(ans, (S - a + 1) / C[i] + ((S - a + 1) % C[i] > 0)); } ans.writeln; }