There are N camels numbered 1 through N.
The weight of Camel i is w_i.
You will arrange the camels in a line and make them cross a bridge consisting of M parts.
Before they cross the bridge, you can choose their order in the line - it does not have to be Camel 1, 2, \ldots, N from front to back - and specify the distance between each adjacent pair of camels to be any non-negative real number.
The camels will keep the specified distances between them while crossing the bridge.
The i-th part of the bridge has length l_i and weight capacity v_i.
If the sum of the weights of camels inside a part (excluding the endpoints) exceeds v_i, the bridge will collapse.
Determine whether it is possible to make the camels cross the bridge without it collapsing. If it is possible, find the minimum possible distance between the first and last camels in the line in such a case.
It can be proved that the answer is always an integer, so print an integer.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 8
 - 1 \leq M \leq 10^5
 - 1 \leq w_i,l_i,v_i \leq 10^8

-----Input-----
Input is given from Standard Input in the following format:
N M
w_1 w_2 \cdots w_N
l_1 v_1
\vdots
l_M v_M

-----Output-----
If the bridge will unavoidably collapse when the camels cross the bridge, print -1.
Otherwise, print the minimum possible distance between the first and last camels in the line when the camels cross the bridge without it collapsing.

-----Sample Input-----
3 2
1 4 2
10 4
2 6

-----Sample Output-----
10

 - It is possible to make the camels cross the bridge without it collapsing by, for example, arranging them in the order 1, 3, 2 from front to back, and setting the distances between them to be 0, 10.
 - For Part 1 of the bridge, there are moments when only Camel 1 and 3 are inside the part and moments when only Camel 2 is inside the part. In both cases, the sum of the weights of camels does not exceed 4 - the weight capacity of Part 1 - so there is no collapse.
 - For Part 2 of the bridge, there are moments when only Camel 1 and 3 are inside the part and moments when only Camel 2 is inside the part. In both cases, the sum of the weights of camels does not exceed 6 - the weight capacity of Part 2 - so there is no collapse.
 - Note that the distance between two camels may be 0 and that camels on endpoints of a part are not considered to be inside the part.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
import sys
input = sys.stdin.readline
from itertools import permutations, accumulate
import heapq
import bisect
from operator import itemgetter

def dijkstra(start, edge):
	n = len(edge)
	dist = [0] * n
	que = [(0, start)]
	while que:
		(d, v) = heapq.heappop(que)
		if dist[v] < d:
			continue
		for (nv, nd) in edge[v]:
			if dist[nv] > d + nd:
				dist[nv] = d + nd
				heapq.heappush(que, (dist[nv], nv))
	return dist
(n, m) = map(int, input().split())
W = tuple(map(int, input().split()))
LV = sorted((tuple(map(int, input().split())) for _ in range(m)), key=itemgetter(1))
(L, V) = zip(*LV)
P = [0]
w_max = max(W)
for (l, v) in LV:
	if w_max > v:
		print(-1)
		return
	if P[-1] > l:
		P.append(P[-1])
	else:
		P.append(l)

def f(K):
	S = list(accumulate((W[k] for k in K)))
	edge = [[] for _ in range(n)]
	for i in range(n - 1):
		edge[i + 1].append((i, 0))
	for i in range(n - 1):
		for j in range(i + 1, n):
			if i == 0:
				t = S[j]
			else:
				t = S[j] - S[i - 1]
			p = P[bisect.bisect_left(V, t)]
			edge[j].append((i, -p))
	return -dijkstra(n - 1, edge)[0]
ans = float('inf')
for K in permutations(range(n)):
	ans = min(ans, f(K))
print(ans)


import sys
from operator import itemgetter
from itertools import permutations
from bisect import bisect_left
(N, M) = list(map(int, input().split()))
W = list(map(int, input().split()))
P = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
if max(W) > min(P, key=itemgetter(1))[1]:
	print(-1)
	return
P.sort(key=itemgetter(1), reverse=True)
P.sort(key=itemgetter(0))
INF = float('inf')
minV = [INF] * M
for i in range(M - 1, 0, -1):
	minV[i - 1] = min(minV[i], P[i][1])
bridge_l = [0]
bridge_v = [0]
for (i, (l, v)) in enumerate(P):
	if v < minV[i]:
		bridge_l.append(l)
		bridge_v.append(v)
ans = INF
for C in permutations(list(range(N))):
	H = [0] * (N + 1)
	for i in range(N):
		H[i] = H[i - 1] + W[C[i]]
	pos = [0] * N
	for i in range(1, N):
		for j in range(i, -1, -1):
			w = H[i] - H[j - 1]
			idx = bisect_left(bridge_v, w)
			pos[i] = max(pos[i], bridge_l[idx - 1] + pos[j])
	ans = min(ans, pos[N - 1])
print(ans)


import sys, itertools, bisect
input = sys.stdin.readline
(N, M) = list(map(int, input().split()))
W = [int(w) for w in input().split()]
maxW = max(W)
lv = [list(map(int, input().split())) for _ in range(M)]
lv.sort(key=lambda x: (x[1], -x[0]))
LV = [lv[0]]
for (l, v) in lv:
	if maxW > v:
		print(-1)
		return
	if LV[-1][0] < l:
		LV.append([l, v])
LV.sort(key=lambda x: x[1])
V = [v for (_, v) in LV]
L = [l for (l, _) in LV]
ans = float('inf')
for perm in itertools.permutations(list(range(N)), N):
	dist = [0] * (N + 1)
	for i in range(1, N):
		ww = W[perm[i]]
		for j in range(1, i + 1):
			ww += W[perm[i - j]]
			idx = bisect.bisect_left(V, ww) - 1
			if idx == -1:
				length = 0
			else:
				length = L[idx]
			dist[i + 1] = max(dist[i + 1], dist[i - j + 1] + length)
	ans = min(ans, dist[-1])
print(ans)


import bisect
from itertools import permutations
(N, M) = map(int, input().split())
w = list(map(int, input().split()))
bridge = []
for i in range(M):
	(l, W) = map(int, input().split())
	bridge.append((W, l))
bridge.sort()
if min((bridge[i][0] for i in range(M))) < max(w):
	print(-1)
	return ()
Max = [bridge[i][1] for i in range(M)]
for i in range(1, M):
	Max[i] = max(Max[i], Max[i - 1])
data = [0 for i in range(2 ** N)]
for i in range(2 ** N):
	tmp = 0
	for j in range(N):
		if i >> j & 1:
			tmp += w[j]
	idx = bisect.bisect_left(bridge, (tmp, -1))
	if idx == 0:
		data[i] = 0
	else:
		data[i] = Max[idx - 1]
per = list(permutations([i for i in range(N)]))
res = 10 ** 18
for L in per:
	dp = [0 for i in range(N)]
	for i in range(N - 2, -1, -1):
		tmp = 1 << L[i]
		for j in range(i + 1, N):
			tmp += 1 << L[j]
			dp[i] = max(dp[i], dp[j] + data[tmp])
	res = min(res, dp[0])
print(res)


import sys
input = sys.stdin.readline
from operator import itemgetter
import bisect
(N, M) = list(map(int, input().split()))
W = list(map(int, input().split()))
B = [tuple(map(int, input().split())) for i in range(M)]
MIN = 1 << 60
for (l, v) in B:
	MIN = min(MIN, v)
if MIN < max(W):
	print(-1)
	return
B2 = []
for (x, y) in B:
	B2.append([y, x])
B2.sort(key=itemgetter(0))
B3 = [B2[0]]
for (x, y) in B2[1:]:
	if y <= B3[-1][1]:
		continue
	else:
		B3.append([x, y])
B3 = [[0, 0]] + B3
B3.append([1 << 60, B3[-1][1]])
from itertools import permutations
L = list(permutations(list(range(N))))
ANS = 1 << 60
for l in L:
	W2 = [W[l[i]] for i in range(N)]
	DP = [0] * (N + 1)
	for i in range(N):
		S = W2[i]
		for j in range(i + 1, N):
			S += W2[j]
			x = bisect.bisect(B3, [S, 0])
			DP[j] = max(DP[j], DP[i] + B3[x - 1][1])
	ANS = min(ANS, DP[N - 1])
print(ANS)


import bisect, collections, copy, heapq, itertools, math, string
import sys

def I():
	return int(sys.stdin.readline().rstrip())

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def S():
	return sys.stdin.readline().rstrip()

def LS():
	return list(sys.stdin.readline().rstrip().split())
from collections import deque, defaultdict, Counter
import heapq
from functools import reduce
from itertools import permutations
import math
import bisect

def bellman_ford(s, n, g):
	d = [float('inf')] * n
	d[s] = 0
	for i in range(n):
		update = False
		for (x, y, z) in g:
			if d[y] > d[x] + z:
				d[y] = d[x] + z
				update = True
		if not update:
			break
		if i == n - 1:
			return -1
	return d

def main():
	(N, M) = MI()
	W = LI()
	V_list = []
	V_list_ = []
	Parts = defaultdict()
	for i in range(M):
		(l, v) = MI()
		Parts[i] = (l, v)
		V_list.append((v, i))
		V_list_.append(v)
	V_list.sort(key=lambda tup: tup[0])
	V_list_.sort()
	max_len_list = [0]
	maxlen = 0
	for i in range(M):
		if Parts[V_list[i][1]][0] > maxlen:
			maxlen = Parts[V_list[i][1]][0]
		max_len_list.append(maxlen)
	bit_list = []
	for i in range(1, 2 ** N):
		A_bit = '{:0>{}b}'.format(i, N)
		bit_list.append(A_bit)
	camel_len_dict = defaultdict()
	for bits in bit_list:
		cnt = 0
		weight = 0
		for (i, bit) in enumerate(bits):
			if bit == '1':
				cnt += 1
				weight += W[i]
		a = bisect.bisect_left(V_list_, weight)
		if cnt == 1 and a != 0:
			print(-1)
			return
		camel_len_dict[weight] = max_len_list[a]
	camel_number = []
	for i in range(N):
		camel_number.append(i)
	P = itertools.permutations(camel_number)
	ans_list = []
	bit_list_ = []
	for i in range(2 ** (N - 1)):
		B_bit = '{:0>{}b}'.format(i, N - 1)
		bit_list_.append(B_bit)
	for p in P:
		weight_p_list = []
		weight_p = 0
		for p_ in p:
			weight_p += W[p_]
			weight_p_list.append(weight_p)
		C = []
		for i in range(N):
			for j in range(i + 1, N):
				if i != 0:
					C.append([i, j, -camel_len_dict[weight_p_list[j] - weight_p_list[i - 1]]])
				else:
					C.append([i, j, -camel_len_dict[weight_p_list[j]]])
		ans_list.append(bellman_ford(0, N, C)[-1])
	print(-max(ans_list))

def __starting_point():
	main()
__starting_point()


import sys
import itertools
import bisect
(n, m) = map(int, input().split())
w = list(map(int, input().split()))
lv = [map(int, input().split()) for _ in range(m)]
(l, v) = [list(i) for i in zip(*lv)]
if min(w) > min(v):
	print('-1')
	return
l = [i for (_, i) in sorted(zip(v, l))]
v.sort()
len_rm = list(itertools.accumulate(l, max))
ans = float('inf')
for W in itertools.permutations(w):
	length = [0] * n
	for i in range(n):
		w_ij = W[i]
		for j in range(i + 1, n):
			w_ij += W[j]
			idx = bisect.bisect_left(v, w_ij)
			if idx == 0:
				x_ij = 0
			else:
				x_ij = len_rm[idx - 1]
			length[j] = max(length[j], length[i] + x_ij)
			if idx == m:
				break
	ans = min(ans, length[-1])
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
(n, m) = list(map(int, input().split()))
w = list(map(int, input().split()))
lv = []
lm = -1
for i in range(m):
	lv.append(tuple(map(int, input().split())))
	lm = max(lm, lv[-1][0])
from operator import itemgetter
lv.sort(key=itemgetter(1))
nlv = [(0, 0), lv[0]]
for (l, v) in lv:
	if l <= nlv[-1][0]:
		continue
	nlv.append((l, v))
vs = [nlv[i][1] for i in range(len(nlv))]
from bisect import bisect_left as bl, bisect_right as br

def sub(x):
	ind = bl(vs, x - 0.5)
	if ind == 0:
		return 0
	return nlv[ind - 1][0]

def cumsum(a):
	c = 0
	n = len(a)
	a.insert(0, 0)
	for i in range(1, n + 1):
		a[i] = a[i - 1] + a[i]
	return a
if nlv[-1][1] < max(w):
	ans = -1
else:
	from itertools import permutations
	l = list(range(n))
	ans = float('inf')
	for ps in permutations(l):
		cum = cumsum([w[ps[i]] for i in range(n)])
		if sub(cum[1]) == float('inf'):
			continue
		ls = [0]
		for i in range(1, n):
			val = max((ls[ii] + sub(cum[i + 1] - cum[ii]) for ii in range(i)))
			ls.append(val)
		ans = min(ans, ls[-1])
	if ans > 10 ** 20:
		ans = -1
print(ans)


import itertools
import bisect
(N, M) = map(int, input().split())
W = list(map(int, input().split()))
V = []
for i in range(M):
	(l, v) = map(int, input().split())
	V.append((l, v))
V.sort(key=lambda x: x[1])
V2 = [V[i][1] for i in range(M)]
V3 = [V[i][0] for i in range(M)]
V4 = []
x = 0
for i in range(M):
	x = max(x, V3[i])
	V4.append(x)
b = V4[M - 1]
if max(W) > min(V2):
	print(-1)
	return
ans = 10 ** 20
for k in list(itertools.permutations(range(N))):
	x = [W[k[i]] for i in range(N)]
	A = [[0] * N for _ in range(N)]
	for m in list(itertools.combinations(range(N), 2)):
		s = min(m[0], m[1])
		e = max(m[0], m[1])
		a = bisect.bisect_left(V2, sum(x[s:e + 1]))
		if a == 0:
			A[s][e] = 0
		elif a == M:
			A[s][e] = b
		else:
			A[s][e] = V4[a - 1]
	dp = [0] * N
	for i in range(1, N):
		for j in range(i):
			dp[i] = max(dp[i], dp[j] + A[j][i])
	if ans > dp[N - 1]:
		ans = dp[N - 1]
print(ans)


from itertools import permutations
(N, M, *I) = map(int, open(0).read().split())
(W, LV) = (I[:N], list(zip(*[iter(I[N:])] * 2)))
if any((w > v for (_, v) in LV for w in W)):
	print(-1)
	return
L = [0] * (1 << N)
for i in range(1 << N):
	s = sum((w for (j, w) in enumerate(W) if i >> j & 1))
	L[i] = max((l for (l, v) in LV if s > v), default=0)
ans = float('inf')
for P in permutations(range(N)):
	dp = [0] * N
	for (i, p) in enumerate(P[1:], 1):
		t = 1 << p
		for j in reversed(range(i)):
			t |= 1 << P[j]
			dp[i] = max(dp[i], dp[j] + L[t])
	ans = min(ans, dp[-1])
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
import itertools
import bisect
(n, m) = list(map(int, input().split()))
w = list(map(int, input().split()))
g = [list(map(int, input().split())) for i in range(m)]
g.sort(key=lambda x: x[1])
L = [0]
V = []
x = 0
for i in range(m):
	if g[i][0] > x:
		L.append(g[i][0])
		V.append(g[i][1])
		x = g[i][0]
w.sort()
if w[-1] > g[0][1]:
	print(-1)
	return
ANS = float('inf')
for v in itertools.permutations(w):
	dp = [0] * n
	dp[0] = 0
	for i in range(1, n):
		cnt = v[i]
		for j in range(i - 1, -1, -1):
			cnt += v[j]
			vv = bisect.bisect_left(V, cnt)
			dp[i] = max(dp[i], dp[j] + L[vv])
	ANS = min(ANS, dp[-1])
print(ANS)


from bisect import bisect_left
from itertools import permutations
INF = 10 ** 12

def main():
	(N, M) = list(map(int, input().split()))
	w = list(map(int, input().split()))
	LV = [[0, 0]]
	for _ in range(M):
		(l, v) = list(map(int, input().split()))
		LV.append([v, l])
	LV.sort()
	V = [0]
	LV2 = [[0, 0]]
	now = 0
	for a in LV:
		if a[1] > now:
			now = a[1]
			LV2.append(a)
			V.append(a[0])
	if V[1] < max(w):
		print(-1)
		return
	ans = INF
	for p in permutations(list(range(N))):
		dp = [0] * N
		dp[0] = 0
		for i in range(1, N):
			wsum = w[p[i]]
			for j in range(i - 1, -1, -1):
				wsum += w[p[j]]
				d = bisect_left(V, wsum)
				dp[i] = max(dp[i], dp[j] + LV2[d - 1][1])
		ans = min(ans, dp[N - 1])
	print(ans)

def __starting_point():
	main()
__starting_point()


import sys
from bisect import bisect_left
from collections import namedtuple
from itertools import permutations
input = sys.stdin.readline
(N, M) = list(map(int, input().split()))
W = [int(x) for x in input().split()]
P = [tuple(map(int, input().split())) for _ in range(M)]
P.sort(key=lambda part: part[1])
ls = [p[0] for p in P]
vs = [p[1] for p in P]
for i in range(1, M):
	ls[i] = max(ls[i - 1], ls[i])
if max(W) > min(vs):
	print(-1)
	return
ans = 10 ** 20
for ws in permutations(sorted(W)):
	pref = [ws[0]]
	for i in range(1, N):
		pref.append(pref[i - 1] + ws[i])
	dp = [0] * N
	for i in range(N):
		for j in range(i):
			interval = pref[i] - (pref[j - 1] if j >= 1 else 0)
			idx = bisect_left(vs, interval)
			need = ls[idx - 1] if idx >= 1 else 0
			dp[i] = max(dp[i], dp[j] + need)
	ans = min(ans, dp[-1])
print(ans)


import itertools
import bisect
(n, m) = list(map(int, input().split()))
w = list(map(int, input().split()))
g = [list(map(int, input().split())) for _ in range(m)]
g.sort(key=lambda x: x[1])
L = []
V = []
init = 0
for i in range(m):
	if g[i][0] > init:
		L.append(g[i][0])
		V.append(g[i][1])
		init = g[i][0]
w.sort()
if w[0] > g[0][1]:
	print(-1)
	return
ans = float('inf')
for v in itertools.permutations(w):
	dp = [0] * n
	for i in range(1, n):
		cnt = v[i]
		for j in range(i - 1, -1, -1):
			cnt += v[j]
			bisect_v = bisect.bisect_left(V, cnt)
			if bisect_v - 1 >= len(L) or bisect_v - 1 < 0:
				continue
			dp[i] = max(dp[i], dp[j] + L[bisect_v - 1])
	ans = min(ans, dp[-1])
print(ans)


from bisect import bisect_left
from itertools import permutations
(N, M) = map(int, input().split())
w = list(map(int, input().split()))
lv = [list(map(int, input().split())) for i in range(M)]
lv.sort(key=lambda x: x[1])
l = [0]
v = [0]
for (li, vi) in lv:
	if vi == v[-1]:
		l[-1] = max(l[-1], li)
	elif li > l[-1]:
		l.append(li)
		v.append(vi)
if v[1] < max(w):
	print(-1)
	return

def solve(order):
	x = [-1] * N
	x[0] = 0
	for i in range(1, N):
		w_now = order[i]
		for j in range(i - 1, -1, -1):
			w_now += order[j]
			space = l[bisect_left(v, w_now) - 1]
			x[i] = max(x[i], x[j] + space)
	return x[-1]
ans = float('inf')
for order in permutations(w):
	ans = min(ans, solve(order))
print(ans)


from itertools import permutations
from bisect import *
(N, M) = list(map(int, input().split()))
w = list(map(int, input().split()))
lv = [list(map(int, input().split())) for _ in range(M)]
w.sort()
lv.sort(key=lambda x: x[1])
seq = list(range(N))
x = list(permutations(seq))
vs = [0]
ls = [0]
ans = float('inf')
ma = 0
flag = 1
for i in range(M):
	ma = max(ma, lv[i][0])
	vs.append(lv[i][1])
	ls.append(ma)
for i in range(N):
	if w[i] > lv[0][1]:
		flag = 0
for tuples in x:
	cuml = [0]
	buf = 0
	for i in tuples:
		buf = buf + w[i]
		cuml.append(buf)
	disttable = [[0] * N for _ in range(N)]
	dist = [0] * N
	for i in range(N + 1):
		for j in range(i + 2, N + 1):
			weight = cuml[j] - cuml[i]
			ind = bisect_left(vs, weight)
			disttable[i][j - 1] = ls[ind - 1]
	for i in range(N):
		for j in range(i + 1, N):
			dist[j] = max(dist[j], dist[i] + disttable[i][j])
	ans = min(ans, dist[N - 1])
if flag == 1:
	print(ans)
else:
	print(-1)


from bisect import bisect_left
from itertools import permutations
(n, m) = map(int, input().split())
w = list(map(int, input().split()))
lv = [list(map(int, input().split()))[::-1] for i in range(m)]
lv.sort()
(l, v) = ([l_ for (v_, l_) in lv], [v_ for (v_, l_) in lv])
if max(w) > min(v):
	print(-1)
	return ()
for i in range(1, m):
	l[i] = max(l[i - 1], l[i])
l.append(0)
ans = float('inf')
for p in permutations(range(n), r=n):
	w2 = [w[w_] for w_ in p]
	lis = [0]
	now = w2[0]
	for i in range(1, n):
		now += w2[i]
		cur = now
		cnt = 0
		for j in range(i):
			ind = bisect_left(v, cur) - 1
			cnt = max(cnt, lis[j] + l[ind])
			cur -= w2[j]
		lis.append(cnt)
	ans = min(ans, lis[-1])
print(ans)


(N, M) = map(int, input().split())
W = list(map(int, input().split()))
LV = [tuple(map(int, input().split())) for i in range(M)]
maxw = max(W)
if any((maxw > v for (l, v) in LV)):
	print(-1)
	return
LV.sort(key=lambda x: x[1] * 10 ** 9 - x[0])
vl = [(0, 0)]
maxl = 0
for (l, v) in LV:
	if l <= maxl:
		continue
	maxl = l
	vl.append((v, l))
from itertools import permutations
from bisect import bisect
ans = float('inf')
for ptn in permutations(W):
	cw = [0]
	for w in ptn:
		cw.append(cw[-1] + w)
	cl = [0]
	for i in range(2, N + 1):
		nl = 0
		for j in range(i - 1):
			w = cw[i] - cw[j]
			k = bisect(vl, (w, -1))
			l = vl[k - 1][1]
			pl = cl[i - 2] - cl[j]
			nl = max(nl, l - pl)
		cl.append(cl[-1] + nl)
	ans = min(ans, cl[-1])
print(ans)


from itertools import permutations
from bisect import bisect_left, bisect_right
(n, m) = map(int, input().split())
w = list(map(int, input().split()))
lu = [list(map(int, input().split())) for _ in range(m)]
lu.sort(key=lambda x: x[1])
lu = [[0, lu[0][1]]] + lu
l = []
u = []
for (ll, uu) in lu:
	u.append(uu)
	if len(l):
		l.append(max(ll, l[-1]))
	else:
		l.append(ll)
if max(w) > min(u):
	print(-1)
	return
ans = 10 ** 20
for p in permutations(w):
	x = [0] + list(p)
	for i in range(n):
		x[i + 1] += x[i]
	dp = [0] * n
	for i in range(n - 1):
		for j in range(i + 1, n):
			s = x[j + 1] - x[i]
			ll = l[max(bisect_left(u, s) - 1, 0)]
			dp[j] = max(dp[j], dp[i] + ll)
	ans = min(ans, dp[n - 1])
print(ans)


import sys
from itertools import permutations
from bisect import bisect_left
(N, M) = list(map(int, input().split()))
W = list(map(int, input().split()))
P = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
INF = float('inf')
if max(W) > min((v for (_, v) in P)):
	print(-1)
	return
P.sort(key=lambda x: (x[0], -x[1]))
cur = INF
bridge_l = []
bridge_v = []
for (l, v) in reversed(P):
	if v < cur:
		bridge_l.append(l)
		bridge_v.append(v)
		cur = v
bridge_l.append(0)
bridge_v.append(0)
bridge_l.reverse()
bridge_v.reverse()
ans = INF
for C in permutations(W):
	H = [0] * (N + 1)
	for (i, c) in enumerate(C):
		H[i] = H[i - 1] + c
	pos = [0] * N
	for i in range(1, N):
		for j in range(i):
			w = H[i] - H[j - 1]
			idx = bisect_left(bridge_v, w)
			pos[i] = max(pos[i], pos[j] + bridge_l[idx - 1])
	ans = min(ans, pos[N - 1])
print(ans)


def main():
	(n, m) = list(map(int, input().split()))
	w = list(map(int, input().split()))
	lv = [list(map(int, input().split())) for _ in [0] * m]
	min_v = 10 ** 15
	for (l, v) in lv:
		min_v = min(min_v, v)
	if min_v < max(w):
		print(-1)
		return 0
	w_list = [-1]
	l_list = [0]
	lv.sort(key=lambda x: (x[1], -x[0]))
	for (l, v) in lv:
		if w_list[-1] != v:
			w_list.append(v)
			l_list.append(max(l, l_list[-1]))
		else:
			l_list[-1] = max(l, l_list[-1])
	from itertools import permutations
	from bisect import bisect_left as bl
	perm = permutations(w)
	ans = 10 ** 15
	for p in perm:
		d = [[0] * n for _ in [0] * n]
		for i in range(n - 1):
			for j in range(i + 1, n):
				weight = sum(p[i:j + 1])
				b = bl(w_list, weight) - 1
				d[i][j] = max(d[i][j], l_list[b])
		dist = [0] * n
		for i in range(1, n):
			for j in range(i):
				if dist[i] - dist[j] < d[j][i]:
					dist[i] = dist[j] + d[j][i]
		ans = min(ans, dist[-1])
	print(ans)
main()


import itertools
import bisect
(n, m) = map(int, input().split())
w = tuple(map(int, input().split()))
lv = []
for i in range(m):
	(l, v) = map(int, input().split())
	lv.append([v, l])
lv.sort(key=lambda x: (x[0], -x[1]))
for wi in w:
	if wi > lv[0][0]:
		print(-1)
		return
mx = 0
for i in range(m):
	mx = max(lv[i][1], mx)
	lv[i][1] = mx
lv = [[0, 0]] + lv
b = {}

def f(x):
	if x in b:
		return b[x]
	else:
		b[x] = bisect.bisect_left(lv, [x, 0])
		return b[x]
ans = float('inf')
for p in itertools.permutations(range(n)):
	dp = [[0 for _ in range(n)] for _ in range(n)]
	for i in range(n - 1):
		for j in range(i + 1, n):
			ww = 0
			for k in range(i, j + 1):
				ww += w[p[k]]
			idx = f(ww)
			dp[i][j] = lv[idx - 1][1]
	for i in range(1, n):
		for j in range(i):
			dp[0][i] = max(dp[0][j] + dp[j][i], dp[0][i])
	ans = min(dp[0][n - 1], ans)
print(ans)


import itertools
import bisect
(N, M) = [int(n) for n in input().split()]
W = [int(n) for n in input().split()]
bridges = [[int(n) for n in input().split()] for _ in range(M)]
bridges.sort(key=lambda x: x[1])
limits = [v for (l, v) in bridges]
len_rm = list(itertools.accumulate([l for (l, v) in bridges], max))
ans = -1
if max(W) <= min(limits):
	ans = 1000000000
	for W_perm in itertools.permutations(W):
		lengths = [0 for _ in range(N)]
		for i in range(N):
			w_ij = W_perm[i]
			for j in range(i + 1, N):
				w_ij += W_perm[j]
				idx = bisect.bisect_left(limits, w_ij)
				if idx == 0:
					x_ij = 0
				else:
					x_ij = len_rm[idx - 1]
				lengths[j] = max(lengths[j], lengths[i] + x_ij)
				if idx == M:
					break
		candidate = lengths[-1]
		ans = min(ans, candidate)
print(ans)


from itertools import permutations
from bisect import bisect_left as B
(N, M) = list(map(int, input().split()))
W = list(map(int, input().split()))
vls = []
for _ in range(M):
	(l, v) = list(map(int, input().split()))
	vls.append((v, l))
vls.sort()
rm = [0] * (M + 1)
vs = []
for (i, (v, l)) in enumerate(vls):
	rm[i + 1] = max(rm[i], l)
	vs.append(v)
R = 10 ** 18
for w in permutations(W, N):
	md = [0] * N
	for i in range(N):
		hw = w[i]
		if B(vs, hw):
			R = -1
		for j in range(i + 1, N):
			hw += w[j]
			md[j] = max(md[j], md[i] + rm[B(vs, hw)])
	R = min(R, md[-1])
print(R)


from sys import stdin
import math
import itertools
readline = stdin.readline
(n, m) = list(map(int, readline().split()))
weights = list(map(int, readline().split()))
bridges = [list(map(int, readline().split())) for _ in [0] * m]
bridges.sort()
bridges_filtered = []
bridges_filtered.append(bridges[m - 1])
current_strongest_conditon_bridge = bridges[m - 1]
bridges_filtered_len = 1
for i in range(m - 2, -1, -1):
	bridge = bridges[i]
	if bridge[1] < current_strongest_conditon_bridge[1]:
		bridges_filtered.append(bridge)
		bridges_filtered_len += 1
		current_strongest_conditon_bridge = bridge
if current_strongest_conditon_bridge[1] < max(weights):
	print('-1')
	return

def acceptable_min_len(w):
	(l, r) = (0, bridges_filtered_len - 1)
	while l <= r:
		mid = (l + r) // 2
		if bridges_filtered[mid][1] >= w:
			l = mid + 1
		else:
			r = mid - 1
	return bridges_filtered[l][0] if l <= bridges_filtered_len - 1 else 0

def min_len(seq):
	dp = [0] * (n + 1)
	cusum_wight = [0]
	for i in seq:
		cusum_wight.append(cusum_wight[-1] + weights[i])
	for i in range(2, n + 1):
		for j in range(1, i):
			weight_between_i_j = cusum_wight[i] - cusum_wight[j - 1]
			min_len_i_j = acceptable_min_len(weight_between_i_j)
			dp[i] = max(dp[i], dp[j] + min_len_i_j)
	return dp[-1]
base = list(range(n))
combinations = itertools.permutations(base)
print(min(list(map(min_len, combinations))))


import itertools
import bisect

def f(i):
	if i == n:
		k = 0
		sumw = 0
		for j in range(n):
			if s[j]:
				k += pow2[j]
				sumw += w[j]
		sumwlist[k] = sumw
		return
	s[i] = 1
	f(i + 1)
	s[i] = 0
	f(i + 1)
	return
(n, m) = map(int, input().split())
w = list(map(int, input().split()))
vl = []
vlist = []
for _ in range(m):
	(l, v) = map(int, input().split())
	vl.append([v, l])
vl.sort()
for (v, l) in vl:
	vlist.append(v)
if vlist[0] < max(w):
	print(-1)
	return
maxl = [0] * (m + 1)
for i in range(m):
	maxl[i + 1] = max(maxl[i], vl[i][1])
s = [0] * n
pow2 = [1] * n
for i in range(n - 1):
	pow2[i + 1] = 2 * pow2[i]
sumwlist = [0] * (2 * pow2[-1] + 5)
f(0)
okl = [0] * (2 * pow2[-1] + 5)
for i in range(2 * pow2[-1]):
	okl[i] = maxl[bisect.bisect_left(vlist, sumwlist[i])]
ans = 1145141919810
for p in itertools.permutations(pow2):
	p = list(p)
	q = [0] * (n + 1)
	for i in range(n):
		q[i + 1] = p[i] + q[i]
	dp = [[0] * (n - 1) for _ in range(n - 1)]
	for i in range(n - 1):
		dp[0][i] = okl[q[i + 2] - q[i]]
	for i in range(1, n - 1):
		for j in range(n - 1 - i):
			dp[i][j] = okl[q[i + j + 2] - q[j]]
			for k in range(1, i + 1):
				dp[i][j] = max(dp[i][j], dp[k - 1][j] + dp[i - k][j + k])
	ans = min(ans, dp[n - 2][0])
print(ans)


import sys
from itertools import permutations
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
(N, M) = list(map(int, input().split()))
w = list(map(int, input().split()))
lv = [tuple(map(int, input().split())) for _ in range(M)]

def solve(w, lv):
	if max(w) > min((_[1] for _ in lv)):
		return -1
	lv.sort(key=lambda x: x[1])
	vs = []
	ls = []
	for (l, v) in lv:
		if len(ls) == 0 or l > ls[-1]:
			vs.append(v)
			ls.append(l)
	ans = -2
	for p in permutations(w):
		cum_weights = [0]
		positions = [0]
		for (i, wi) in enumerate(p):
			cum_weights.append(cum_weights[-1] + wi)
			if i == 0:
				continue
			next_pos = positions[-1]
			for j in range(i):
				intarval_weight = cum_weights[i + 1] - cum_weights[j]
				critical_bridge = bisect_left(vs, intarval_weight) - 1
				if critical_bridge >= 0:
					next_pos = max(next_pos, positions[j] + ls[critical_bridge])
			positions.append(next_pos)
		if ans == -2:
			ans = positions[-1]
		else:
			ans = min(ans, positions[-1])
	return ans
print(solve(w, lv))


import sys
from itertools import permutations, accumulate
from bisect import bisect_left

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c for j in range(b)] for i in range(a)]

def list3d(a, b, c, d):
	return [[[d for k in range(c)] for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return list(map(int, input().split()))

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** (-10)
(N, M) = MAP()
W = LIST()
VL = [(0, 0)]
for i in range(M):
	(l, v) = MAP()
	VL.append((v, l))
VL.sort()
V = [0] * (M + 1)
L = [0] * (M + 1)
for i in range(1, M + 1):
	V[i] = VL[i][0]
	L[i] = max(VL[i][1], L[i - 1])
if max(W) > min(V[1:]):
	print(-1)
	return
ans = INF
for perm in permutations(W):
	acc = [0] + list(accumulate(perm))
	dp = [0] * N
	for l in range(N):
		for r in range(l + 1, N):
			sm = acc[r + 1] - acc[l]
			idx = bisect_left(V, sm) - 1
			dp[r] = max(dp[r], dp[l] + L[idx])
	ans = min(ans, dp[N - 1])
print(ans)


import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
	(N, M) = map(int, readline().split())
	W = list(map(int, readline().split()))
	w_max = max(W)
	mat = []
	for _ in range(M):
		(l, v) = map(int, readline().split())
		if v < w_max:
			return print(-1)
		mat.append((l, v))
	from operator import itemgetter
	mat.sort(key=itemgetter(0), reverse=True)
	mat.sort(key=itemgetter(1))
	L = [0]
	V = [0]
	m = 0
	for i in range(M):
		(l, v) = mat[i]
		m = max(m, l)
		L.append(m)
		V.append(v)
	from itertools import permutations
	import bisect
	ans = INF
	for per in permutations(range(N)):
		a = [W[i] for i in per]
		b = [[0] * N for _ in range(N)]
		for i in range(N - 1):
			cur = a[i]
			for j in range(i + 1, N):
				cur += a[j]
				p = bisect.bisect_left(V, cur)
				b[i][j] = L[p - 1]
		dp = [0] * N
		for i in range(N - 1):
			cur = dp[i]
			for j in range(i + 1, N):
				dp[j] = max(dp[j], cur + b[i][j])
		ans = min(ans, dp[N - 1])
	print(ans)

def __starting_point():
	main()
__starting_point()


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
from itertools import permutations, combinations

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write('\n'.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
INF = float('inf')
mod = int(1000000000.0) + 7
(n, m) = mdata()
w = mdata()
part = sorted([mdata() for i in range(m)], key=lambda x: x[1])
part1 = [part[0][1]]
part2 = [0, part[0][0]]
for i in range(1, m):
	part1.append(part[i][1])
	part2.append(max(part2[-1], part[i][0]))
if min(part1) < max(w):
	out(-1)
	return
perm = list(permutations(w))
ans = INF
for lis in perm:
	dp = [0] * n
	for i in range(n):
		ind = i
		k = lis[i]
		for j in range(i + 1, n):
			k += lis[j]
			dp[j] = max(dp[j], dp[i] + part2[bl(part1, k)])
	ans = min(ans, dp[-1])
out(ans)


import sys
from itertools import permutations, accumulate
from operator import itemgetter
import bisect

def input():
	return sys.stdin.readline().rstrip()

def trans(l_2d):
	return [list(x) for x in zip(*l_2d)]

def main():
	(n, m) = list(map(int, input().split()))
	camel = list(map(int, input().split()))
	bridge = [list(map(int, input().split())) for i in range(m)]
	bridge.sort(key=itemgetter(1))
	bridge = trans(bridge)
	bridge[0] = list(accumulate(bridge[0], func=max, initial=0))
	if max(camel) > min(bridge[1]):
		print(-1)
		return
	ans = 10 ** 15
	for permut in permutations(camel):
		graph = [[0] * n for _ in range(n)]
		for i in range(n - 1):
			for j in range(i + 1, n):
				weight = sum(permut[i:j + 1])
				graph[i][j] = bridge[0][bisect.bisect_left(bridge[1], weight)]
		dist = [0] * n
		for i in range(1, n):
			mindist = 0
			for j in range(i):
				mindist = max(dist[j] + graph[j][i], mindist)
			dist[i] = mindist
		ans = min(ans, dist[-1])
	print(ans)

def __starting_point():
	main()
__starting_point()


from itertools import permutations
from bisect import bisect_left, bisect_right
(N, M) = list(map(int, input().split()))
W = list(map(int, input().split()))
L = [tuple(map(int, input().split())) for _ in range(M)]
L.sort(key=lambda x: x[1])
length = [0]
weights = [0]
for (l, w) in L:
	if l >= length[-1] and w >= weights[-1]:
		length.append(l)
		weights.append(w)
if max(W) > weights[1]:
	print(-1)
	return
ans = 10 ** 10
for p in permutations(list(range(N))):
	rows = [0] * N
	V = [0]
	for i in range(N):
		V.append(V[-1] + W[p[i]])
	for i in range(N):
		for j in range(i + 1, N):
			w = V[j + 1] - V[i]
			rows[j] = max(rows[j], rows[i] + length[bisect_left(weights, w) - 1])
	if ans > rows[-1]:
		ans = rows[-1]
print(ans)


import sys
import bisect
from itertools import permutations, accumulate
input = sys.stdin.readline
(N, M) = list(map(int, input().split()))
W = list(map(int, input().split()))
LV = [list(map(int, input().split())) for i in range(M)]
VL = [(v, l) for (l, v) in LV]
VL.sort()
(V, L) = list(zip(*VL))
if max(W) > min(V):
	print(-1)
	return
L = [0] + list(accumulate(L, max))
ans = 10 ** 20
for order in permutations(list(range(N))):
	NW = [W[i] for i in order]
	t = [0, NW[0]]
	p = [0]
	for nw in NW[1:]:
		t.append(t[-1] + nw)
		ps = []
		for (np, nt) in zip(p, t[:-2]):
			ind = bisect.bisect_left(V, t[-1] - nt)
			ps.append(np + L[ind])
		p.append(max(ps))
	ans = min(ans, p[-1])
print(ans)


from bisect import bisect_left
from collections import namedtuple
from itertools import permutations
(n, m) = map(int, input().split())
w = list(map(int, input().split()))
P = [tuple(map(int, input().split())) for _ in range(m)]
P.sort(key=lambda x: x[1])
ls = [p[0] for p in P]
vs = [p[1] for p in P]
for i in range(1, m):
	ls[i] = max(ls[i - 1], ls[i])
if max(w) > min(vs):
	print(-1)
	return
ans = float('inf')
for ws in permutations(w):
	pref = [ws[0]]
	for i in range(1, n):
		pref.append(pref[i - 1] + ws[i])
	dp = [0] * n
	for i in range(n):
		for j in range(i):
			interval = pref[i] - (pref[j - 1] if j >= 1 else 0)
			idx = bisect_left(vs, interval)
			need = ls[idx - 1] if idx >= 1 else 0
			dp[i] = max(dp[i], dp[j] + need)
	ans = min(ans, dp[-1])
print(ans)


from itertools import permutations
from bisect import bisect_left
(n, m) = list(map(int, input().split()))
w = list(map(int, input().split()))
li = [list(map(int, input().split())) for _ in range(m)]
li.sort(key=lambda x: x[1])
l = [0] * (m + 1)
v = [0] * (m + 1)
for i in range(m):
	(l[i + 1], v[i + 1]) = li[i]
for i in range(m):
	l[i + 1] = max(l[i], l[i + 1])
if max(w) > min(v[1:]):
	print(-1)
else:
	dv = dict()
	for i in range(2 ** n):
		t = 0
		for j in range(n):
			if i >> j & 1:
				t += w[j]
		dv[t] = l[bisect_left(v, t) - 1]
	ans = 10 ** 18
	for p in permutations(w):
		li = [0] * (n + 1)
		for i in range(n):
			li[i + 1] = li[i] + p[i]
		x = [0] * n
		for i in range(n):
			for j in range(i + 1, n + 1):
				x[j - 1] = max(x[j - 1], x[i] + dv[li[j] - li[i]])
		ans = min(ans, x[-1])
	print(ans)


import itertools
import bisect
(n, m) = [int(i) for i in input().split()]
w = [int(i) for i in input().split()]
l_v = []
for i in range(m):
	l_v.append([int(i) for i in input().split()])
l_v.sort(key=lambda x: x[1])
l = []
v = []
max_l = []
max_l_ = 0
for i in range(m):
	l.append(l_v[i][0])
	v.append(l_v[i][1])
	max_l_ = max(l_v[i][0], max_l_)
	max_l.append(max_l_)
if min(v) < max(w):
	print(-1)
	return
x = [0 for j in range(2 ** n)]
for i in itertools.product([0, 1], repeat=n):
	weight = sum([w[_] * i[_] for _ in range(n)])
	a = bisect.bisect_left(v, weight)
	if a >= 1:
		x[sum([2 ** k * i[k] for k in range(n)])] = max_l[a - 1]
ans = float('inf')
for i in itertools.permutations([_ for _ in range(n)]):
	dp = [0 for _ in range(n - 1)]
	dp[0] = x[2 ** i[1] + 2 ** i[0]]
	for j in range(n - 2):
		if j == 0:
			dp[j + 1] = max(dp[j] + x[2 ** i[2] + 2 ** i[1]], x[2 ** i[2] + 2 ** i[1] + 2 ** i[0]])
		else:
			dpp = []
			for k in range(j + 1):
				sumbit = sum([2 ** i[j + 2 - kk] for kk in range(j + 2 - k)])
				dpp.append(dp[k] + x[sumbit])
			sumbit2 = sum([2 ** i[j + 2 - kk] for kk in range(j + 3)])
			dpp.append(x[sumbit2])
			dp[j + 1] = max(dpp)
	ans = min(ans, dp[-1])
print(ans)


from itertools import permutations
from itertools import accumulate
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

def solve():
	INF = 10 ** 15
	(N, M) = list(map(int, input().split()))
	Ws = list(map(int, input().split()))
	LVs = [tuple(map(int, input().split())) for _ in range(M)]
	minV = min([V for (L, V) in LVs])
	if max(Ws) > minV:
		print(-1)
		return
	LVs.sort(key=lambda x: x[1])
	(bdrLs, bdrVs) = ([0], [0])
	maxL = 0
	for (L, V) in LVs:
		if L > maxL:
			bdrLs.append(L)
			bdrVs.append(V)
			maxL = L
	ans = INF
	for Camels in permutations(Ws, N):
		accCamels = [0] + list(accumulate(Camels))
		Lss = [[INF] * N for _ in range(N)]
		for i in range(N):
			if Camels[i] > minV:
				Lss[i][i] = INF
			else:
				Lss[i][i] = 0
			for j in range(i + 1, N):
				wgt = accCamels[j + 1] - accCamels[i]
				iV = bisect_left(bdrVs, wgt) - 1
				Lss[i][j] = bdrLs[iV]
		costs = [0] * N
		for i in range(1, N):
			cost = 0
			for j in range(i + 1):
				c2 = costs[j] + Lss[j][i]
				if c2 > cost:
					cost = c2
			costs[i] = cost
		if costs[-1] < ans:
			ans = costs[-1]
	if ans == INF:
		print(-1)
	else:
		print(ans)
solve()


import sys
input = sys.stdin.readline

def I():
	return int(input())

def MI():
	return list(map(int, input().split()))

def LI():
	return list(map(int, input().split()))
mod = 10 ** 9 + 7
inf = 10 ** 10
(N, M) = MI()
W = LI()
LV = [[0, 0] for _ in range(M)]
mV = inf
for i in range(M):
	(LV[i][0], LV[i][1]) = MI()
	mV = min(mV, LV[i][1])
if max(W) > mV:
	print(-1)
	return
LV.sort(reverse=True)
nVL = [(0, 0)]
MV = inf
for i in range(M):
	(l, v) = LV[i]
	if v < MV:
		nVL.append((v, l))
		MV = v
nVL.sort()
from collections import defaultdict
dd = defaultdict(int)
import bisect

def calc(x):
	if dd[x]:
		return dd[x]
	temp = (x, -1)
	num = bisect.bisect_left(nVL, temp) - 1
	(v, l) = nVL[num]
	dd[x] = l
	return l
import itertools
ans = inf
for ite in itertools.permutations(list(range(N)), N):
	Cs = []
	for i in ite:
		Cs.append(W[i])
	S = [0] * (N + 1)
	for i in range(N):
		S[i + 1] = S[i] + Cs[i]
	X = [0] * N
	for i in range(N):
		for j in range(i + 1, N):
			w = S[j + 1] - S[i]
			l = calc(w)
			X[j] = max(X[j], X[i] + l)
	temp = X[-1]
	ans = min(ans, temp)
print(ans)


from itertools import permutations
from bisect import bisect_left
import sys
INF = float('inf')
(N, M) = map(int, input().split())
W = list(map(int, input().split()))
L = [0] * M
V = [0] * M
for i in range(M):
	(L[i], V[i]) = map(int, input().split())
if max(W) > min(V):
	print(-1)
	return
ZIP = zip(V, L)
ZIP = sorted(ZIP)
(V, L) = zip(*ZIP)
R = [0] * M
R[0] = L[0]
for i in range(M - 1):
	R[i + 1] = max(R[i], L[i + 1])
ans = float('inf')
for l in permutations(W, N):
	dp = [0] * N
	CUMSUM = [0]
	for i in l:
		CUMSUM.append(CUMSUM[-1] + i)
	for i in range(N - 1):
		for j in range(i + 2, N + 1):
			tmp = CUMSUM[j] - CUMSUM[i]
			index = bisect_left(V, tmp)
			if index == 0:
				dp[j - 1] = max(dp[j - 1], dp[i])
			else:
				dp[j - 1] = max(dp[j - 1], dp[i] + R[index - 1])
	ans = min(ans, dp[-1])
print(ans)


from bisect import bisect_left
from itertools import permutations
from operator import itemgetter

def solve(n, m, www, lv):
	lv.sort(key=itemgetter(1))
	if lv[0][1] < max(www):
		return -1
	lll = [0]
	vvv = [0]
	for (l, v) in lv:
		if v == vvv[-1]:
			lll[-1] = max(lll[-1], l)
		elif l > lll[-1]:
			lll.append(l)
			vvv.append(v)
	ans = 10 ** 18
	for order in permutations(list(range(n))):
		dists = [0] * n
		for oi in range(n - 1):
			d = dists[oi]
			total_weight = www[order[oi]]
			for oj in range(oi + 1, n):
				total_weight += www[order[oj]]
				k = bisect_left(vvv, total_weight) - 1
				dists[oj] = max(dists[oj], d + lll[k])
		ans = min(ans, dists[-1])
	return ans
(n, m) = list(map(int, input().split()))
www = list(map(int, input().split()))
lv = [tuple(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, www, lv)
print(ans)


import sys
import itertools
import bisect
input = sys.stdin.readline
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(m)]
edges.append([0, 0])
edges = sorted(edges, key=lambda x: x[0])
ls = []
ws = []
for i in range(m - 1, -1, -1):
	edges[i][1] = min(edges[i][1], edges[i + 1][1])
for (l, w) in edges:
	ls.append(l)
	ws.append(w)
if max(arr) > ws[1]:
	print(-1)
	return
ans = 10 ** 18
for p in itertools.permutations(range(n)):
	tmp = [0] * n
	for i in range(n):
		tmp[i] = arr[p[i]]
	tans = [0] * (n - 1)
	for r in range(1, n):
		for l in range(0, r):
			w = sum(tmp[l:r + 1])
			pos = bisect.bisect_left(ws, w)
			tans[r - 1] = max(tans[r - 1], ls[pos - 1] - sum(tans[l:r - 1]))
	ans = min(ans, sum(tans))
print(ans)


import sys
from itertools import permutations
from bisect import bisect_left
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():
	(n, m) = list(map(int, input().split()))
	W = list(map(int, input().split()))
	LV = [list(map(int, input().split())) for _ in range(m)]
	max_w = max(W)
	min_v = min([LV[i][1] for i in range(m)])
	if min_v < max_w:
		print(-1)
		return
	LV.sort(key=lambda x: x[1])
	L = [0, LV[0][0]]
	V = [0, LV[0][1]]
	for (l, v) in LV[1:]:
		if l <= L[-1]:
			continue
		else:
			L.append(l)
			V.append(v)
	L.append(L[-1])
	V.append(f_inf)
	res = f_inf
	for pattern in permutations(W):
		dp = [0] * n
		for i in range(n):
			sum_w = pattern[i]
			for j in range(i + 1, n):
				sum_w += pattern[j]
				idx = bisect_left(V, sum_w)
				dp[j] = max(dp[j], dp[i] + L[idx - 1])
		res = min(res, dp[-1])
	print(res)

def __starting_point():
	resolve()
__starting_point()


from itertools import permutations
from bisect import bisect_left

def main():
	inf = float('inf')
	(n, m) = map(int, input().split())
	weight = sorted(list(map(int, input().split())))
	bridge = [tuple(map(int, input().split())) for _ in range(m)]
	bridge.sort(key=lambda x: x[1])
	bridge_w = [x[1] for x in bridge]
	bridge_l = [0] * (m + 1)
	for i in range(m):
		bridge_l[i + 1] = max(bridge[i][0], bridge_l[i])
	if weight[-1] > bridge_w[0]:
		print(-1)
		return
	mn = inf
	for x in permutations(weight):
		dis = [[0] * n for _ in range(n)]
		for i in range(1, n):
			for j in range(n - i):
				work_weight = sum(x[j:j + i + 1])
				work_index = bisect_left(bridge_w, work_weight)
				mx = bridge_l[work_index]
				for l in range(1, i):
					if dis[j][j + l] + dis[j + l][j + i] > mx:
						mx = dis[j][j + l] + dis[j + l][j + i]
				dis[j][j + i] = mx
		if dis[0][n - 1] < mn:
			mn = dis[0][n - 1]
	print(mn)
main()


import sys
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
YesNo = lambda b: bool([print('Yes')] if b else print('No'))
YESNO = lambda b: bool([print('YES')] if b else print('NO'))
int1 = lambda x: int(x) - 1
from itertools import permutations
from bisect import bisect_left, bisect_right
(N, M) = map(int, input().split())
w = tuple(map(int, input().split()))
MAX_W = max(w)
lv = [() for _ in range(M)]
for i in range(M):
	(l, v) = map(int, input().split())
	lv[i] = (l, v)
	if v < MAX_W:
		print(-1)
		return
lv.sort(key=lambda a: (a[1], -a[0]))
(L, V) = ([], [])
tmp_l = 0
for (l, v) in lv:
	if tmp_l < l:
		tmp_l = l
		L.append(l)
		V.append(v)
ans = INF
for tmp_w in permutations(w):
	edge = [[] for _ in range(N)]
	S = [0] * (N + 1)
	for i in range(N):
		S[i + 1] = S[i] + tmp_w[i]
	for i in range(N - 1):
		for j in range(i + 1, N):
			SUM = S[j + 1] - S[i]
			res = bisect_left(V, SUM)
			if res > 0:
				edge[i].append((j, L[res - 1]))
			else:
				edge[i].append((j, 0))
	dp = [0] * N
	for i in range(N):
		for (j, l) in edge[i]:
			dp[j] = max(dp[j], dp[i] + l)
	ans = min(ans, dp[-1])
print(ans)


import itertools
import bisect
(N, M) = [int(n) for n in input().split()]
W = [int(n) for n in input().split()]
bridges = [[int(n) for n in input().split()] for _ in range(M)]
bridges.sort(key=lambda x: x[1])
limits = [v for (l, v) in bridges]
len_rm = list(itertools.accumulate([l for (l, v) in bridges], max))
ans = -1
if max(W) <= min(limits):
	w2x = dict()
	for F in itertools.product([0, 1], repeat=N):
		w = sum([w for (w, f) in zip(W, F) if f == 1])
		if w in w2x:
			continue
		idx = bisect.bisect_left(limits, w)
		w2x[w] = 0 if idx == 0 else len_rm[idx - 1]
	ans = 1000000000
	for W_perm in itertools.permutations(W):
		lengths = [0 for _ in range(N)]
		for i in range(N):
			w_ij = W_perm[i]
			for j in range(i + 1, N):
				w_ij += W_perm[j]
				lengths[j] = max(lengths[j], lengths[i] + w2x[w_ij])
				if w_ij > limits[-1]:
					break
		candidate = lengths[-1]
		ans = min(ans, candidate)
print(ans)


(n, m) = map(int, input().split())
(*w,) = map(int, input().split())
llvv = [tuple(map(int, input().split())) for _ in range(m)]
ww = max(w)
vv = min((x[1] for x in llvv))
if ww > vv:
	print(-1)
	return
llvv.sort(key=lambda x: x[1])
v = [0] + [vi for (li, vi) in llvv]
l = [0] + [li for (li, vi) in llvv]
for i in range(m):
	l[i + 1] = max(l[i], l[i + 1])
INF = 10 ** 15
from itertools import permutations
from bisect import bisect_left
ans = INF
for p in permutations(range(n)):
	dist = [0 for _ in range(n)]
	for i in range(n):
		tmp = w[p[i]]
		for j in range(i + 1, n):
			tmp += w[p[j]]
			t = bisect_left(v, tmp)
			if t:
				dist[j] = max(dist[j], dist[i] + l[t - 1])
			else:
				dist[j] = max(dist[j], dist[i])
	ans = min(ans, dist[-1])
print(ans)


from itertools import permutations
from functools import lru_cache
(N, M) = map(int, input().strip().split())
weights = list(map(int, input().strip().split()))
c = []
min_weight = float('inf')
for _ in range(M):
	(l, v) = map(int, input().strip().split())
	min_weight = min(v, min_weight)
	c.append([l, v])
if min_weight < max(weights):
	print('-1')
else:
	min_weight = float('inf')
	c.sort()
	for i in range(M - 1, -1, -1):
		min_weight = min(min_weight, c[i][1])
		c[i][1] = min_weight

	@lru_cache(None)
	def bisect(val):
		(l, r) = (0, M - 1)
		while l <= r:
			mid = (l + r) // 2
			if c[mid][1] < val:
				l = mid + 1
			else:
				r = mid - 1
		return c[r][0] if r >= 0 else 0

	def compute(sequence):
		dp = [0] * (N + 1)
		prefix_sum = [0]
		for i in sequence:
			prefix_sum.append(prefix_sum[-1] + weights[i])
		for i in range(2, N + 1):
			for j in range(1, i):
				dp[i] = max(dp[i], dp[j] + bisect(prefix_sum[i] - prefix_sum[j - 1]))
		return dp[-1]
	base = list(range(N))
	print(min(map(compute, permutations(base))))


printn = lambda x: print(x, end='')
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
ins = lambda : input().strip()
DBG = True
BIG = 10 ** 18
R = 10 ** 9 + 7

def ddprint(x):
	if DBG:
		print(x)
import itertools, bisect
(n, m) = inm()
w = inl()
vl = []
vs = []
for i in range(m):
	(l, v) = inm()
	vl.append((v, l))
	vs.append(v)
if max(w) > min(vs):
	print(-1)
	return
w.sort()
vl.sort()
b = []
mx = -1
for i in range(m):
	mx = max(mx, vl[i][1])
	if len(b) > 0 and b[-1][0] == vl[i][0]:
		b.pop()
	b.append((vl[i][0], mx))
pms = itertools.permutations(w[:-2], n - 2)
mn = BIG
for pm in pms:
	pml = list(pm)
	pml.append(w[n - 2])
	a = [0]
	ww = [w[n - 1]]
	for i in range(n - 1):
		x = a[-1]
		u = pml[i]
		for k in range(i, -1, -1):
			u += ww[k]
			p = bisect.bisect_left(b, (u, -1))
			if p > 0 and b[p - 1][1] > x - a[k]:
				x = a[k] + b[p - 1][1]
		a.append(x)
		ww.append(pml[i])
	mn = min(mn, a[-1])
print(mn)