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: interview

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)]
#橋の選別　ネックとなる橋の抽出　lj<=li,vj>=vi となる橋jはiに統合可能
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)#i番目までのラクダの必要距離 というか　座標

    for i in range(1,N):#iは終わりのインデックス　i含む
        ww = W[perm[i]]
        for j in range(1,i+1):#jは間隔。1つまえ~先頭までみていくので1~iまで
            ww +=W[perm[i-j]]#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 # 自身への距離は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()
    #print(V_list)
    #print(V_list_)
    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)
    #print(max_len_list)
    bit_list = []
    for i in range(1, 2 ** N):
        A_bit = "{:0>{}b}".format(i, N)
        bit_list.append(A_bit)
    #print(bit_list)
    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]
        #print(camels)
        a = bisect.bisect_left(V_list_, weight)
        if cnt == 1 and a != 0:
            print(-1)
            return
        camel_len_dict[weight] = max_len_list[a]
    #print(camel_len_dict)
    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:
        #print(p, 'p')
        weight_p_list = []
        weight_p = 0
        for p_ in p:
            weight_p += W[p_]
            weight_p_list.append(weight_p)
        #print(weight_p_list)
        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]])])
        #print(C, 'C')
        ans_list.append(bellman_ford(0, N, C)[-1])
    #print(ans_list)
    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)]
#lv = [list(map(int, input().split())) for _ in range(m)]

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):
    """※ aを破壊する
    l[i] = sum(a[:i]) なるlを返す
    sum(a[i:j]) == l[j+1] - l[i]
    """
    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 = ls[i-1]+lm
            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)


#!/usr/bin/env python3
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
    # N!通りを全探索する
    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 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)]
#橋の選別　ネックとなる橋の抽出　lj<=li,vj>=vi となる橋jはiに統合可能
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])
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)#i番目までのラクダの必要距離 というか　座標

    for i in range(1,N):#iは終わりのインデックス　i含む
        ww = W[perm[i]]
        for j in range(1,i+1):#jは間隔。1つまえ~先頭までみていくので1~iまで
            ww +=W[perm[i-j]]#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)


# from itertools import permutations
# N, M = map(int, input().split())
# W = list(map(int, input().split()))

# L = []
# V = []
# for _ in range(M):
#     l, v = map(int, input().split())
#     L.append(l)
#     V.append(v)

# # どのようにしても箸が落ちる時
# if min(W) > min(V):
#     print(-1)
#     return

# ans = float('inf')
# for v in permutations(W):
#     dp = [0] * N
#     for i in range(N):
#         for j in range(i + 1, N):
#             weight = v[i] + v[j]
#             for m in range(M):
#                 if weight > V[m]:
#                     dp[j] = max(dp[j], dp[j - 1] + L[m])
#     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))
#print(lv,w)
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)
#print(ls,vs)

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)
    #print(cuml)
    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)
            #print(weight,ind)
            disttable[i][j-1]=ls[ind-1]
    #print(disttable)
    for i in range(N):
        for j in range(i+1,N):
            dist[j]=max(dist[j],dist[i]+disttable[i][j])
        #print(dist)
    #input()
    #print()
    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)

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 < 0:
                continue
            dp[i] = max(dp[i], dp[j] + L[bisect_v - 1])
    ans = min(ans, dp[-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(p,dp)
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[i][j]:iとjの必要な距離
        d = [[0]*n for _ in [0]*n]
        for i in range(n-1):
            for j in range(i+1, n):
                #print(i, j)
                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()


# C - Camels and Bridge
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]))
# print(lv)
for wi in w:
  if wi > lv[0][0]:
    print(-1)
    return
mx = 0
# より耐荷重が小さいパーツの長さが優先される。
# 耐荷重4長さ10と耐荷重7長さ5のパーツがあったら、後者のパーツは無視される。
# (重量7でも10の間隔が必要)
for i in range(m):
  mx = max(lv[i][1],mx)
  lv[i][1] = mx
# lv.append([float('inf'),lv[-1][1]])
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[i][j]:とらなければいけないi番目のラクダからj番目のラクダまで間隔の最小値
  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 = bisect.bisect_left(lv,[ww,0])
      idx = f(ww)
      # print(ww,idx,lv)
      dp[i][j] = lv[idx-1][1]
  # 例えば0,j,i番目のラクダについて考えると、0とiの間隔は
  # dp[0][i]とdp[0][j]+dp[j][i]の長い方にする必要がある。
  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 sys
input = sys.stdin.readline
from operator import itemgetter
import bisect

N,M=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(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 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)] # [length_i, weight_i] 

# sort by weight
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)) # running maximum
# len_rm[i]: the maximum length of the bridges whose load limit <= limits[i]

ans = -1
if max(W) <= min(limits):
    ans = 1000000000 # larger than maximum possible solution (7 x 10^8)
    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] # w_ij: total weight between i and j (inclusive)
                idx = bisect.bisect_left(limits, w_ij)
                if idx == 0: # all bridge accepts w_ij
                    x_ij = 0
                else: # bridges[0] ... bridges[i-1] cannot accept w_ij
                    x_ij = len_rm[idx-1]
                lengths[j] = max(lengths[j], lengths[i] + x_ij)

                # skipping trivial edges
                # even without this if-block, we can get AC
                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)



# -*- coding: utf-8 -*-

from sys import stdin
import math
import itertools
readline = stdin.readline
#n = int(readline())
#n, m = map(int, readline().split())
#a = list(map(int, readline().split()))
#l = [list(map(int, readline().split())) for _ in [0]*m]
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()

# 長い順に橋の条件を見ていき、不要なものを取り除く処理
# 着目している橋Aについて、自分より長いかつ耐荷重が小さい橋Xが存在
# => Aの耐荷重条件はXの条件を満たせ自動的に満たされるので、Aは不要
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

# ラクダ1頭で最も厳しい橋の耐荷重オーバーになるなら条件を満たすラクダ列は不可能
# 一番重いラクダ一頭だけ確認すれば十分
if current_strongest_conditon_bridge[1] < max(weights):
    print("-1")
    return


def acceptable_min_len(w):
    """
    重さwに耐えうる長さで最短のものを二分探索
    """
    l, r = 0, bridges_filtered_len - 1
    # bridges_filteredは長い順、耐荷重が大きい順となっている
    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):
    """
    seqはラクダの配列(並び替え済み)
    その配列で可能な最小の長さを返す
    """
    # dp[i]はi番目のラクダまで条件を満たすように並べた最小の長さ
    # dp[i] = iより前の全てのラクダとの区間において、橋をこわなさいような最小の長さを満たす
    dp = [0]*(n+1)
    # 重さの累積和。i-j番目のラクダの重さの総和を求めるのに使用
    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,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)]
#橋の選別　ネックとなる橋の抽出　lj<=li,vj>=vi となる橋jはiに統合可能
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)#i番目までのラクダの必要距離 というか　座標
    #wgt = [0]*(N+1)#i-1番目までのラクダの重さの累積和
    #wgt[1] = W[perm[0]]
    for i in range(1,N):#iは終わりのインデックス　i含む
        #wgt[i+1]=wgt[i]+W[perm[i]]
        ww = W[perm[i]]
        for j in range(1,i+1):
            #toW = wgt[i+1]-wgt[j]
            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)


from bisect import bisect_left
from collections import namedtuple
from itertools import permutations

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 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
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
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')
#from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+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)

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)

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)]
#橋の選別　ネックとなる橋の抽出　lj<=li,vj>=vi となる橋jはiに統合可能
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)#i番目までのラクダの必要距離 というか　座標
    wgt = [0]*(N+1)#i-1番目までのラクダの重さの累積和
    wgt[1] = W[perm[0]]
    for i in range(1,N):#iは終わりのインデックス　i含む
        wgt[i+1]=wgt[i]+W[perm[i]]
        for j in range(i):
            toW = wgt[i+1]-wgt[j]
            idx = bisect.bisect_left(V,toW)-1
            if idx == -1:
                length = 0
            else:
                length = L[idx]
            dist[i]=max(dist[i],dist[j]+length)
    ans = min(ans,dist[-1])

print(ans)


#!/usr/bin/env python3
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))
    #print(bridge)
    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)] #n以下の個数を数える
        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(dist)
    print(ans)        




def __starting_point():
    main()

__starting_point()

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)] # [length_i, weight_i] 

# sort by weight
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)) # running maximum
# len_rm[i]: the maximum length of the bridges whose load limit <= limits[i]

ans = -1
if max(W) <= min(limits):
    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] # w_ij: total weight between i and j (inclusive)
                idx = bisect.bisect_left(limits, w_ij)
                if idx == 0: # all bridge accepts w_ij
                    x_ij = 0
                else: # bridges[0] ... bridges[i-1] cannot accept w_ij
                    x_ij = len_rm[idx-1]
                lengths[j] = max(lengths[j], lengths[i] + x_ij)
            
        candidate = lengths[-1]
        if ans == -1:
            ans = candidate
        else:
            ans = min(ans, candidate)

print(ans)


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の組を入力し、vの昇順でソート
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をそれぞれ分けて格納（後々vの値で二分探索したいので）
2頭のラクダが通れる橋を後々二分探索する
その時にlの累積maxであるmax_lを用いる
"""

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

"""
n頭の合計重さweightを耐えられない橋の中で最も距離が長い橋を記録する
2分探索で求めたindex（n頭のラクダの合計の重さを耐えられる端の中で最も強度が弱いもの）
より前のindexの橋（ラクダの重さを耐えられない橋）の中で最も距離が大きい橋の長さ
→max_lを使う！
"""

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]

"""
ラクダの並び方全n!の組合せにおいて、それぞれDPによって取らなければいけない距離を計算し、その最小値をansとする
"""
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):
                # print(i,j, k, [i[j + 1 - kk] for kk in range(j+2-k)])
                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()
# print(nVL)

from collections import defaultdict
dd = defaultdict(int)

import bisect
def calc(x):
    # 重さxの塊に対して，最低でどれだけの距離が必要か
    
    if dd[x]:
        return dd[x]
    
    temp=(x,-1)
    num=bisect.bisect_left(nVL,temp) - 1
    
    # print(x,temp,num)
    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
        
    # N個の頂点だと考えて，それぞれの座標を決める
    for i in range(N):
        for j in range(i+1,N):
            # i番目とj番目の間の距離
            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)
            


    



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)))


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 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)] # [length_i, weight_i] 

# sort by weight
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)) # running maximum
# len_rm[i]: the maximum length of the bridges whose load limit <= limits[i]

ans = -1
if max(W) <= min(limits):
    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] # w_ij: total weight between i and j (inclusive)
                idx = bisect.bisect_left(limits, w_ij)
                if idx == 0: # all bridge accepts w_ij
                    x_ij = 0
                else: # bridges[0] ... bridges[i-1] cannot accept w_ij
                    x_ij = len_rm[idx-1]
                lengths[j] = max(lengths[j], lengths[i] + x_ij)

                if idx == M:
                    break
            
        candidate = lengths[-1]
        if ans == -1:
            ans = candidate
        else:
            ans = min(ans, candidate)

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 bisect import bisect_left
from itertools import permutations
from operator import itemgetter


def solve(n, 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(www):
        dists = [0] * n
        for i in range(n - 1):
            d = dists[i]
            total_weight = order[i]
            for j in range(i + 1, n):
                total_weight += order[j]
                k = bisect_left(vvv, total_weight) - 1
                dists[j] = max(dists[j], 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, www, lv)
print(ans)


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]
    #i番目に脆い橋が渡れるとき取れる長さの最も短い値
    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):
        #iとjのラクダが離れていなければならない距離をdis
        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
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()))

def main():
    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()
    # print(nVL)
    
    from collections import defaultdict
    dd = defaultdict(int)
    
    import bisect
    def calc(x):
        # 重さxの塊に対して，最低でどれだけの距離が必要か
        
        if dd[x]:
            return dd[x]
        
        temp=(x,-1)
        num=bisect.bisect_left(nVL,temp) - 1
        
        # print(x,temp,num)
        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
            
        # N個の頂点だと考えて，それぞれの座標を決める
        for i in range(N):
            for j in range(i+1,N):
                # i番目とj番目の間の距離
                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)
                
    
    
     
    
    

main()


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)

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:
    d = [0 for i in range(N)]
    for i in range(1,N):
        tmp = 1<<L[i]
        for j in range(i-1,-1,-1):
            tmp += 1<<L[j]
            d[i] = max(d[i],data[tmp]+d[j])
    res = min(res,d[-1])

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)

    #if W2!=[857,849,806,57,608,244,349,513]:
    #    continue

    for i in range(N):
        for j in range(i+1,N):
            S=sum(W2[i:j+1])
            x=bisect.bisect(B3,[S,0])

            DP[j]=max(DP[j],DP[i]+B3[x-1][1])

        #print(W2,S,x,DP)
            
            
    #if W2==[857,849,806,57,608,244,349,513]:
    #    print(W2,DP)
                
    ANS=min(ANS,DP[N-1])
print(ANS)
            
    


# -*- coding: utf-8 -*-
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)] # [length_i, load_limit_i] 

# sort by load limit
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)) # running maximum
# len_rm[i]: the maximum length of the bridges whose load limit <= limits[i]

ans = -1
if max(W) <= min(limits):
    # precompute mapping
    # from: (sum of) weights, (w)
    # to: maximum part length (x) whose load limit <= w
    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 # larger than maximum possible solution (7 x 10^8)
    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] # w_ij: total weight between i and j (inclusive)
                lengths[j] = max(lengths[j], lengths[i] + w2x[w_ij])

                # skipping trivial edges
                # even without this if-block, we can get AC
                if w_ij > limits[-1]:
                    break
            
        candidate = lengths[-1]
        ans = min(ans, candidate)

print(ans)


#n<=8
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):  # we can never pas
    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))))

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])
    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()


#from collections import deque,defaultdict
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 # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

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]:
                    #ddprint(f"add l {j=} {k=} {l=} {u=} {v=}")
                    x = a[k]+b[p-1][1]
        a.append(x)
        ww.append(pml[i])
    #ddprint(pml)
    #ddprint(a)
    mn = min(mn,a[-1])
print(mn)


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)] # [length_i, weight_i] 

# sort by weight
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)) # running maximum
# len_rm[i]: the maximum length of the bridges whose load limit <= limits[i]

ans = -1
if max(W) <= min(limits):
    ans = 1000000000 # larger than maximum possible solution (7 x 10^8)
    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] # w_ij: total weight between i and j (inclusive)
                idx = bisect.bisect_left(limits, w_ij)
                if idx == 0: # all bridge accepts w_ij
                    x_ij = 0
                else: # bridges[0] ... bridges[i-1] cannot accept w_ij
                    x_ij = len_rm[idx-1]
                lengths[j] = max(lengths[j], lengths[i] + x_ij)

                # skipping trivial edges
                # even without this if-block, we can get AC
                if idx == M:
                    break
            
        candidate = lengths[-1]
        ans = min(ans, candidate)

print(ans)