The only difference between easy and hard versions is constraints.

Ivan plays a computer game that contains some microtransactions to make characters look cooler. Since Ivan wants his character to be really cool, he wants to use some of these microtransactions — and he won't start playing until he gets all of them.

Each day (during the morning) Ivan earns exactly one burle.

There are $n$ types of microtransactions in the game. Each microtransaction costs $2$ burles usually and $1$ burle if it is on sale. Ivan has to order exactly $k_i$ microtransactions of the $i$-th type (he orders microtransactions during the evening).

Ivan can order any (possibly zero) number of microtransactions of any types during any day (of course, if he has enough money to do it). If the microtransaction he wants to order is on sale then he can buy it for $1$ burle and otherwise he can buy it for $2$ burles.

There are also $m$ special offers in the game shop. The $j$-th offer $(d_j, t_j)$ means that microtransactions of the $t_j$-th type are on sale during the $d_j$-th day.

Ivan wants to order all microtransactions as soon as possible. Your task is to calculate the minimum day when he can buy all microtransactions he want and actually start playing.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 1000$) — the number of types of microtransactions and the number of special offers in the game shop.

The second line of the input contains $n$ integers $k_1, k_2, \dots, k_n$ ($0 \le k_i \le 1000$), where $k_i$ is the number of copies of microtransaction of the $i$-th type Ivan has to order. It is guaranteed that sum of all $k_i$ is not less than $1$ and not greater than $1000$.

The next $m$ lines contain special offers. The $j$-th of these lines contains the $j$-th special offer. It is given as a pair of integers $(d_j, t_j)$ ($1 \le d_j \le 1000, 1 \le t_j \le n$) and means that microtransactions of the $t_j$-th type are on sale during the $d_j$-th day.


-----Output-----

Print one integer — the minimum day when Ivan can order all microtransactions he wants and actually start playing.


-----Examples-----
Input
5 6
1 2 0 2 0
2 4
3 3
1 5
1 2
1 5
2 3

Output
8

Input
5 3
4 2 1 3 2
3 5
4 2
2 5

Output
20

Difficulty: introductory

Starter code:

Solutions:
import collections


def main():
    from sys import stdin, stdout

    def read():
        return stdin.readline().rstrip('\n')

    def read_array(sep=None, maxsplit=-1):
        return read().split(sep, maxsplit)

    def read_int():
        return int(read())

    def read_int_array(sep=None, maxsplit=-1):
        return [int(a) for a in read_array(sep, maxsplit)]

    def write(*args, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in args) + end)

    def write_array(array, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in array) + end)

    def enough(days):
        bought = []  # (type, amount)
        bought_total = 0
        used_from = days
        for d in range(days, 0, -1):
            used_from = min(d, used_from)
            for t in offers.get(d, []):
                if K[t] > 0:
                    x = min(K[t], used_from)
                    K[t] -= x
                    bought.append((t, x))
                    bought_total += x
                    used_from -= x
            if not used_from:
                break
        remaining_money = days - bought_total
        ans = (total_transaction - bought_total) * 2 <= remaining_money
        for t, a in bought:
            K[t] += a
        return ans

    n, m = read_int_array()
    K = read_int_array()
    total_transaction = sum(K)
    offers = collections.defaultdict(list)
    for _ in range(m):
        d, t = read_int_array()
        offers[d].append(t-1)

    low = total_transaction
    high = low * 2
    ans = high
    while low <= high:
        mid = (low + high) // 2
        if enough(mid):
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
    write(ans)


main()


import sys
import bisect
import copy
input = sys.stdin.readline

n,m=list(map(int,input().split()))
K=[0]+list(map(int,input().split()))
SP=[list(map(int,input().split())) for i in range(m)]

SP2=[[] for i in range(n+1)]

for d,t in SP:
    SP2[t].append(d)

for i in range(n+1):
    SP2[i].sort()

SUM=sum(K)
MIN=SUM
MAX=SUM*2
MAXBUY=0

for day in range(MIN,MAX+1):

    DAYS=[[] for i in range(day+1)]

    for i in range(n+1):
        x=bisect.bisect_right(SP2[i],day)-1
        if x>=0:
            DAYS[SP2[i][x]].append(i)

    GOLD=0
    SUMK=SUM
    K2=copy.deepcopy(K)

    for d in range(1,day+1):
        GOLD+=1

        for t in DAYS[d]:
            DBUY=min(K2[t],GOLD,SUMK)
            K2[t]-=DBUY
            GOLD-=DBUY


    if GOLD>=sum(K2)*2:
        print(day)
        break




        
        


import sys
import bisect
import copy
input = sys.stdin.readline

n,m=list(map(int,input().split()))
K=[0]+list(map(int,input().split()))
SP=[list(map(int,input().split())) for i in range(m)]

SP2=[[] for i in range(n+1)]

for d,t in SP:
    SP2[t].append(d)

for i in range(n+1):
    SP2[i].sort()

SUM=sum(K)
MIN=SUM
MAX=SUM*2
MAXBUY=0

while MIN!=MAX:
    day=(MIN+MAX)//2

    DAYS=[[] for i in range(day+1)]

    for i in range(n+1):
        x=bisect.bisect_right(SP2[i],day)-1
        if x>=0:
            DAYS[SP2[i][x]].append(i)

    GOLD=0
    SUMK=SUM
    K2=copy.deepcopy(K)

    for d in range(1,day+1):
        GOLD+=1

        for t in DAYS[d]:
            DBUY=min(K2[t],GOLD,SUMK)
            K2[t]-=DBUY
            GOLD-=DBUY


    if GOLD>=sum(K2)*2:
        MAX=day
    else:
        MIN=day+1

print(MIN)




        
        


import math
from collections import defaultdict
import sys
#input = sys.stdin.readline


def main():
    n, m = list(map(int, input().split()))
    k = list(map(int, input().split()))
    sales = [(0, 0)] * m
    for i in range(m):
        a, b = list(map(int, input().split()))
        sales[i] = (b, a)

    def check(days):
        last_sale = {}
        for sale in sales:
            if sale[1] <= days:
                if sale[0] not in last_sale or sale[1] > last_sale[sale[0]]:
                    last_sale[sale[0]] = sale[1]

        date_last_sales = {}
        for t, d in list(last_sale.items()):
            if d not in date_last_sales:
                date_last_sales[d] = [t]
            else:
                date_last_sales[d].append(t)

        balance = 0
        required = [0] + k.copy()

        end = 0
        for d in range(1, days+1):
            balance += 1
            if d in date_last_sales:
                for t in date_last_sales[d]:
                    if required[t] > 0:
                        if required[t] > balance:
                            end += required[t] - balance
                        balance -= min(required[t], balance)
                        required[t] = 0
            if d == days:  # last day
                for r in required:
                    if r > 0:
                        end += r

        return 2*end <= balance

    total = sum(k)
    for i in range(1, 2*total+1):
        if check(i):
            print(i)
            break


def __starting_point():
    main()

__starting_point()

import sys

DEBUG = False

if DEBUG:
    inf = open("input.txt")
else:
    inf = sys.stdin

N, M = list(map(int, inf.readline().split(' ')))
n_items = list(map(int, inf.readline().split(' ')))
sales = []
for _ in range(M):
    sale = list(map(int, inf.readline().split(' ')))
    sales.append(sale)

sales = sorted(sales, key=lambda x: x[0])

# print(N, M)
# print(n_items)
# print(sales)
# last_sales = [0 for _ in range(N)] # last sale day
last_sales = {k: -1 for k in range(N+1)} # for convenience ...
final_sol = 99999999

for i in range(M):
    sale_day, sale_type = sales[i]
    last_sales[sale_type] = sale_day
    if i != M-1: # not last sale
        if sales[i+1][0] == sale_day: # same sale day
            continue
    
    total = 0
    lasts = last_sales.items()
    lasts = sorted(lasts, key=lambda x: x[1]) # sort by day
    burle = 0
    before_lastday = -1
    for stype, last_sday in lasts:
        if stype == 0:
            continue
        if last_sday == -1:
            # non-sale item
            total += n_items[stype-1]*2
            continue
        
        if before_lastday == -1:
            burle = last_sday
        else:
            burle += last_sday - before_lastday
        before_lastday = last_sday

        bought = min(burle, n_items[stype-1])
        left = n_items[stype-1] - bought
        burle -= bought
        total += bought + 2*left
    
    # print(sale_day, total)
    sol = max(sale_day, total)
    if final_sol > sol:
        final_sol = sol

print(final_sol)

import sys

DEBUG = False

if DEBUG:
    inf = open("input.txt")
else:
    inf = sys.stdin

N, M = list(map(int, inf.readline().split(' ')))
n_items = list(map(int, inf.readline().split(' ')))
sales = []
for _ in range(M):
    sale = list(map(int, inf.readline().split(' ')))
    sales.append(sale)

sales = sorted(sales, key=lambda x: x[0])

# print(N, M)
# print(n_items)
# print(sales)
# last_sales = [0 for _ in range(N)] # last sale day
last_sales = {k: -1 for k in range(N+1)} # for convenience ...
final_sol = 99999999

for i in range(M):
    sale_day, sale_type = sales[i]
    last_sales[sale_type] = sale_day
    if i != M-1: # not last sale
        if sales[i+1][0] == sale_day: # same sale day
            continue
    
    total = 0
    lasts = last_sales.items()
    lasts = sorted(lasts, key=lambda x: x[1]) # sort by day
    burle = 0
    before_lastday = -1
    for stype, last_sday in lasts:
        if stype == 0:
            continue
        if last_sday == -1:
            # non-sale item
            total += n_items[stype-1]*2
            continue
        
        if before_lastday == -1:
            burle = last_sday
        else:
            burle += last_sday - before_lastday
        before_lastday = last_sday

        bought = min(burle, n_items[stype-1])
        left = n_items[stype-1] - bought
        burle -= bought
        total += bought + 2*left
    
    # print(sale_day, total)
    sol = max(sale_day, total)
    if final_sol > sol:
        final_sol = sol

print(final_sol)

import sys
import copy

DEBUG = False

if DEBUG:
    inf = open("input.txt")
else:
    inf = sys.stdin

N, M = list(map(int, inf.readline().split(' ')))
n_items = list(map(int, inf.readline().split(' ')))
sales = []
for _ in range(M):
    sale = list(map(int, inf.readline().split(' ')))
    sales.append(sale) # sale_day, sale_type

sales = sorted(sales, key=lambda x: x[0], reverse=True) # sort by day

def can_buy_in(dday):
    used = 0
    money_left = dday
    items = copy.deepcopy(n_items)
    for sale_day, sale_type in sales:
        if sale_day > dday:
            continue
        
        if money_left > sale_day:
            money_left = sale_day
        can_buy = min(items[sale_type-1], money_left)
        # buy it
        used += can_buy
        items[sale_type-1] -= can_buy
        money_left -= can_buy

        if money_left == 0:
            break
    
    need_money_for_rest = sum(items) * 2
    return need_money_for_rest + used <= dday

total_items = sum(n_items)
low = total_items
high = total_items * 2

# find minimum can_buy day
while low <= high:
    mid = (low + high) // 2
    if can_buy_in(mid):
        high = mid-1
    else:
        low = mid+1

print(low)

n, m = input().split()
n = int(n)
m = int(m)
nList = input().split()
bList = [0] * len(nList)
for i in range(len(nList)):
    nList[i] = int(nList[i])
shopD = {}
shopT = {}
oHis = []
mHis = []
maxD = 0
for i in range(m):
    d, t = input().split()
    if nList[int(t) - 1] != 0:
        maxD = max(maxD, int(d))
        if d not in shopD.keys():
            shopD.update({d: [int(t)]})
        else:
            if int(t) not in shopD[d]:
                shopD[d].append(int(t))
        if t not in shopT.keys():
            shopT.update({t: [int(d)]})
        else:
            if int(d) not in shopT[t]:
                shopT[t].append(int(d))
for i, j in shopT.items():
    j = list(dict.fromkeys(j))
    j.sort()
    shopT[i] = j
for i, j in shopD.items():
    j = list(dict.fromkeys(j))
    shopD[i] = j
total = sum(nList)
coin = 0
day = 0
def modifyMis(t, left):
    if left == 0:
        for ii in range(len(mHis))[::-1]:
            if mHis[ii]['t'] == t:
                mHis.pop(ii)
    else:
        for ii in range(len(mHis))[::-1]:
            if mHis[ii]['t'] == t:
                mHis[ii]['n'] = left
while total > 0 and day < maxD:
    coin += 1
    day += 1
    oHis.append({'t': [], 'n': []})
    if str(day) in shopD.keys():
        for t in shopD[str(day)]:
            if nList[t - 1] > 0:
                if bList[t - 1] > 0 and shopT[str(t)][0] != day and coin > nList[t - 1] - bList[t - 1] and len(mHis) > 0 and coin > 0:
                    i = 0
                    j = 0
                    while shopT[str(t)][i] < day:
                        extraC = 0
                        d = shopT[str(t)][i]
                        if t in oHis[d - 1]['t']:
                            indexT = oHis[d - 1]['t'].index(t)
                            extraC += oHis[d - 1]['n'][indexT]
                            bList[t - 1] -= oHis[d - 1]['n'][indexT]
                            total += oHis[d - 1]['n'][indexT]
                            oHis[d - 1]['t'].pop(indexT)
                            oHis[d - 1]['n'].pop(indexT)
                        while j < len(mHis) and mHis[j]['d'] < d:
                            j += 1
                        while extraC > 0 and len(mHis) > j:
                            thisT = mHis[j]['t']
                            thisD = mHis[j]['d']
                            change = min(extraC, mHis[j]['n'])
                            bList[thisT - 1] += change
                            total -= change
                            extraC -= change
                            mHis[j]['n'] -= change
                            modifyMis(thisT, nList[thisT - 1] - bList[thisT - 1])
                            if thisT in oHis[thisD - 1]['t']:
                                oHis[thisD - 1]['n'][oHis[thisD - 1]['t'].index(thisT)] += change
                            else:
                                oHis[thisD - 1]['t'].append(thisT)
                                oHis[thisD - 1]['n'].append(change)
                        i += 1
                        coin += extraC
            buy = min(nList[t - 1] - bList[t - 1], coin)
            if buy != 0:
                oHis[day - 1]['t'].append(t)
                oHis[day - 1]['n'].append(buy)
                total -= buy
                bList[t - 1] += buy
                modifyMis(t, nList[t - 1] - bList[t - 1])  
                coin -= buy
            if nList[t - 1] - bList[t - 1] > 0:
                mHis.append({'d': day, 't': t, 'n': nList[t - 1] - bList[t - 1]}) 
    if coin >= total * 2:
        break
day += max(total * 2 - coin, 0)
print(day)

n, m = input().split()
n = int(n)
m = int(m)
nList = input().split()
bList = [0] * len(nList)
for i in range(len(nList)):
    nList[i] = int(nList[i])
shopD = {}
shopT = {}
oHis = []
mHis = []
maxD = 0
for i in range(m):
    d, t = input().split()
    if nList[int(t) - 1] != 0:
        maxD = max(maxD, int(d))
        if d not in list(shopD.keys()):
            shopD.update({d: [int(t)]})
        else:
            if int(t) not in shopD[d]:
                shopD[d].append(int(t))
        if t not in list(shopT.keys()):
            shopT.update({t: [int(d)]})
        else:
            if int(d) not in shopT[t]:
                shopT[t].append(int(d))
for i, j in list(shopT.items()):
    j = list(dict.fromkeys(j))
    j.sort()
    shopT[i] = j
for i, j in list(shopD.items()):
    j = list(dict.fromkeys(j))
    shopD[i] = j
total = sum(nList)
coin = 0
day = 0
def modifyMis(t, left):
    if left == 0:
        for ii in range(len(mHis))[::-1]:
            if mHis[ii]['t'] == t:
                mHis.pop(ii)
    else:
        for ii in range(len(mHis))[::-1]:
            if mHis[ii]['t'] == t:
                mHis[ii]['n'] = left
while total > 0 and day < maxD:
    coin += 1
    day += 1
    oHis.append({'t': [], 'n': []})
    if str(day) in list(shopD.keys()):
        for t in shopD[str(day)]:
            if nList[t - 1] > 0:
                if bList[t - 1] > 0 and shopT[str(t)][0] != day and coin > nList[t - 1] - bList[t - 1] and len(mHis) > 0 and coin > 0:
                    i = 0
                    j = 0
                    while shopT[str(t)][i] < day:
                        extraC = 0
                        d = shopT[str(t)][i]
                        if t in oHis[d - 1]['t']:
                            indexT = oHis[d - 1]['t'].index(t)
                            extraC += oHis[d - 1]['n'][indexT]
                            bList[t - 1] -= oHis[d - 1]['n'][indexT]
                            total += oHis[d - 1]['n'][indexT]
                            oHis[d - 1]['t'].pop(indexT)
                            oHis[d - 1]['n'].pop(indexT)
                        while j < len(mHis) and mHis[j]['d'] < d:
                            j += 1
                        while extraC > 0 and len(mHis) > j:
                            thisT = mHis[j]['t']
                            thisD = mHis[j]['d']
                            change = min(extraC, mHis[j]['n'])
                            bList[thisT - 1] += change
                            total -= change
                            extraC -= change
                            mHis[j]['n'] -= change
                            modifyMis(thisT, nList[thisT - 1] - bList[thisT - 1])
                            if thisT in oHis[thisD - 1]['t']:
                                oHis[thisD - 1]['n'][oHis[thisD - 1]['t'].index(thisT)] += change
                            else:
                                oHis[thisD - 1]['t'].append(thisT)
                                oHis[thisD - 1]['n'].append(change)
                        i += 1
                        coin += extraC
            buy = min(nList[t - 1] - bList[t - 1], coin)
            if buy != 0:
                oHis[day - 1]['t'].append(t)
                oHis[day - 1]['n'].append(buy)
                total -= buy
                bList[t - 1] += buy
                modifyMis(t, nList[t - 1] - bList[t - 1])  
                coin -= buy
            if nList[t - 1] - bList[t - 1] > 0:
                mHis.append({'d': day, 't': t, 'n': nList[t - 1] - bList[t - 1]}) 
    if coin >= total * 2:
        break
day += max(total * 2 - coin, 0)
print(day)


#binary search reconstructure
  

def BinarySearch(my_list,key):
    l = 0
    r = len(my_list)- 1 
    #print(l,r)
    while r > l :
        mid = (l+r)//2
        if my_list[mid+1] <= key :
            l = mid + 1  
        else :
            r = mid   
        #print(l,r)
    return l

def weather_can_buy(day,total,req_list,sale_days):
    tmp_buy = []
    last_day = []
    # money = day
    # bug anything that is on sale
    d = day
    my_total = total
    for i in range(len(req_list)) : 
        last_day.append(0)
    for i in range(d):
        tmp_buy.append(0)    
    for i in range(len(sale_days)) : 
        if len(sale_days[i]) > 0 : 
            index = BinarySearch(sale_days[i],day)
            last_day[i] = sale_days[i][index]
    for i in range(len(last_day)) :
        if last_day[i]-1 > -1 :
            tmp_buy[last_day[i]-1] += req_list[i]
    # buying
    money = 0
    for i in range(d):
        money += 1
        my_total -= min(money,tmp_buy[i])
        money -= min(money,tmp_buy[i])        
    if my_total < 0 :
        return True
    elif money >= my_total * 2:
        return True
    else :
        return False
    
def function():
    tmp = input().split(" ")
    n = int(tmp[0]) # The number of type
    m = int(tmp[1]) 
    req_list = input().split(" ")
    req_list = list(map(int,req_list)) 
    total = sum(req_list)
    sale_days = []
    # sale days for acceleration
    for i in range(len(req_list)):
        sale_days.append([0])  
    for i in range(m) :
        tmp = input().split(" ")
        dj,tj = (int(tmp[0]),int(tmp[1]))
        sale_days[tj-1].append(dj)
    for i in range(len(sale_days)) :
        sale_days[i] = sorted(sale_days[i])
    # optimized by sorting
    for i in range(len(sale_days)) :
        sale_days[i] = sorted(sale_days[i])     
    #day = 0

    l = 1
    r = 2*total
    while r > l :
        mid = (l+r)//2
        if weather_can_buy(mid,total,req_list,sale_days) :
            r = mid
        else :
            l = mid + 1 
    print(r)
    
function()


import copy
from collections import defaultdict

BIG = 10**9
N, M = [int(i) for i in input().split()]

K = [0] + [int(i) for i in input().split()]

sumK = sum(K)
max_days = 2*sum(K)

day_at_sale_per_item = defaultdict(list)
for i in range(M):
    day, item = [int(i) for i in input().split()]
    day_at_sale_per_item[item].append(day)

sales_per_day = defaultdict(list)
for item, days in list(day_at_sale_per_item.items()):
    for day in days:
        sales_per_day[day].append(item)

L, R = 0, max_days
answer = 0
while L <= R:
    m = (L+R)//2

    def get_best_sales(m):
        best_sales = defaultdict(list)
        for item, days in list(day_at_sale_per_item.items()):
            best_day = 0
            for day in days:
                if day <= m:
                    best_day = max(best_day, day)
            if best_day:
                best_sales[best_day].append(item)
        return best_sales

    def available_sales(m):
        available_money = 0
        nb_sales = 0
        cK = copy.deepcopy(K)

        best_sales = get_best_sales(m)

        for day in range(1, m+1):
            available_money += 1
            for item in best_sales[day]:
                buy = min(cK[item], available_money)
                if buy:
                    cK[item] -= buy
                    available_money -= buy
                    nb_sales += buy
        return nb_sales

    def possible(m):
        total_money = m
        needed_money = 2 * sumK - available_sales(m)
        return total_money >= needed_money

    if possible(m):
        answer = m
        R = m-1
    else:
        L = m+1
print(answer)


from collections import defaultdict

def possible(days):
    nonlocal events, k
    
    latest_ev = defaultdict(int)
    for d, t in events:
        if d <= days:
            latest_ev[t] = max(latest_ev[t], d)
    
    earned = days
    offers_needed = 2 * sum(k) - earned

    offers = 0    
    cur_day = 0
    cur_val = 0
    for t, d in sorted(list(latest_ev.items()), key=lambda x: x[1]):
        cur_val += d - cur_day
        cur_day = d
        offers_to_take = min(k[t], cur_val)
        offers += offers_to_take
        cur_val -= offers_to_take
    return offers >= offers_needed
    

n, m = list(map(int, input().split()))

k = list(map(int, input().split()))

events = []
for _ in range(m):
    d, t = list(map(int, input().split()))
    t -= 1
    events.append((d, t))
    
lo = 0
hi = 4*10**5

while lo + 1 < hi:
    mid = (lo+hi)//2
    
    if possible(mid):
        hi = mid
    else:
        lo = mid
    
print(hi)


from collections import defaultdict

def possible(days):
    nonlocal events, k
    
    latest_ev = defaultdict(int)
    for d, t in events:
        if d <= days:
            latest_ev[t] = max(latest_ev[t], d)
    
    earned = days
    offers_needed = 2 * sum(k) - earned

    offers = 0    
    cur_day = 0
    cur_val = 0
    for t, d in sorted(list(latest_ev.items()), key=lambda x: x[1]):
        cur_val += d - cur_day
        cur_day = d
        offers_to_take = min(k[t], cur_val)
        offers += offers_to_take
        cur_val -= offers_to_take
        if offers >= offers_needed:
            return True
    return offers >= offers_needed
    

n, m = list(map(int, input().split()))

k = list(map(int, input().split()))

events = []
for _ in range(m):
    d, t = list(map(int, input().split()))
    t -= 1
    events.append((d, t))
    
lo = sum(k) - 1
hi = 2 * sum(k)

while lo + 1 < hi:
    mid = (lo+hi)//2
    
    if possible(mid):
        hi = mid
    else:
        lo = mid
    
print(hi)


def check(mid):
	l = [0 for i in range(n)]
	for i in b:
		if(i[0] > mid): break
		l[i[1]-1] = i[0]
	v = [0 for i in range(mid+1)]
	for i in range(n):
		v[l[i]] += a[i]
	ct = 0
	for i in range(1,mid+1):
		ct += 1
		if(ct >= v[i]):
			ct -= v[i]
			v[i] = 0
		else:
			v[i] -= ct
			ct = 0
	return ct >= 2*sum(v)

def bs():
	l = 0
	r = 5*10**5
	while(l <= r):
		mid = (l+r)//2
		if(check(mid)):
			r = mid-1
		else:
			l = mid+1
	return r+1

n,m = map(int,input().split())
a = list(map(int,input().split()))
b = []
for i in range(m):
	b.append(list(map(int,input().split())))
b.sort()
print(bs())

import sys
input = sys.stdin.readline
def check(num):
	last = [0 for i in range(n)]
	for i in o:
		if i[0]>num:
			break
		else:
			last[i[1]-1] = i[0]
	b = [0 for i in range(num+1)]
	for i in range(n):
		b[last[i]] += a[i]

	i = 0
	c = 0
	d = 0
	for i in range(1,num+1):
		c += 1
		if(c >= b[i]):
			c -= b[i]
			b[i] = 0
		else:
			b[i] -= c
			c = 0

	s = sum(b)
	if s*2<=c:
		return True
	return False



n,m = map(int,input().split())
a = list(map(int,input().split()))
o = []
for i in range(m):
	x,y = map(int,input().split())
	o.append((x,y))
o.sort()
low = 1
high = sum(a)*2
while low<high:
	mid = (low+high)//2
	if check(mid):
		high = mid - 1
	else:
		low = mid + 1
if check(low):
	print (low)
else:
	print (low+1)

def check(x):
    last=[0]*(n+1)
    for i in tmp:
        if i[0]>x:
            break
        else:
            last[i[1]]=i[0]
    sal=[0]*(x+1)
    for i in range(1,n+1):
        sal[last[i]]+=lis[i-1]
    c=0
    for i in range(1,x+1):
        c+=1
        if sal[i]>=c:
            sal[i]-=c
            c=0
        else:
            c-=sal[i]
            sal[i]=0
    if sum(sal)*2<=c:
        return True
    else:
        return False        
n,m = list(map(int,input().split()))
lis = list(map(int,input().split()))
tmp=[]
for _ in range(m):
    a,b = list(map(int,input().split()))
    tmp.append([a,b])
tmp.sort()
l=0
r=sum(lis)*2
while l<=r:
    mid = l + (r-l)//2
    if check(mid):
        r = mid-1
    else:
        l = mid+1
if check(r):
    print(r)
elif check(l):
    print(l)
else:
    print(l+1)    





from collections import deque


def main():
    n, m = list(map(int, input().split()))
    wanted_cnt = list(map(int, input().split()))
    Order = [tuple(map(int, input().split())) for i in range(m)]
    #count the maximum number which you can buy on sales day.
    S = sum(wanted_cnt)

    def ispossible_within(Day):
        sale_get_cnt = 0
        last_sale = [0]*n
        for day, good in Order:
            if day > Day:
                continue
            last_sale[good-1] = max(last_sale[good-1], day)
        Que = []
        for i in range(n):
            if wanted_cnt[i] > 0 and last_sale[i] > 0:
                Que.append((last_sale[i], wanted_cnt[i]))
        Que.sort()
        que = deque(Que)
        while que:
            sale_day, wanted = que.popleft()
            money_left = sale_day - sale_get_cnt
            if money_left >= wanted:
                sale_get_cnt += wanted
            elif money_left < wanted:
                sale_get_cnt += money_left
        left_money = Day - sale_get_cnt
        left = S - sale_get_cnt

        return left_money >= 2*left

    impossible = 0
    possible = 2020
    while possible - impossible > 1:
        m = (impossible + possible)//2
        if ispossible_within(m):
            possible = m
        else:
            impossible = m
    print(possible)
    return


def __starting_point():
    main()


__starting_point()