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
[{"code": "import collections\n\n\ndef main():\n    from sys import stdin, stdout\n\n    def read():\n        return stdin.readline().rstrip('\\n')\n\n    def read_array(sep=None, maxsplit=-1):\n        return read().split(sep, maxsplit)\n\n    def read_int():\n        return int(read())\n\n    def read_int_array(sep=None, maxsplit=-1):\n        return [int(a) for a in read_array(sep, maxsplit)]\n\n    def write(*args, **kwargs):\n        sep = kwargs.get('sep', ' ')\n        end = kwargs.get('end', '\\n')\n        stdout.write(sep.join(str(a) for a in args) + end)\n\n    def write_array(array, **kwargs):\n        sep = kwargs.get('sep', ' ')\n        end = kwargs.get('end', '\\n')\n        stdout.write(sep.join(str(a) for a in array) + end)\n\n    def enough(days):\n        bought = []  # (type, amount)\n        bought_total = 0\n        used_from = days\n        for d in range(days, 0, -1):\n            used_from = min(d, used_from)\n            for t in offers.get(d, []):\n                if K[t] > 0:\n                    x = min(K[t], used_from)\n                    K[t] -= x\n                    bought.append((t, x))\n                    bought_total += x\n                    used_from -= x\n            if not used_from:\n                break\n        remaining_money = days - bought_total\n        ans = (total_transaction - bought_total) * 2 <= remaining_money\n        for t, a in bought:\n            K[t] += a\n        return ans\n\n    n, m = read_int_array()\n    K = read_int_array()\n    total_transaction = sum(K)\n    offers = collections.defaultdict(list)\n    for _ in range(m):\n        d, t = read_int_array()\n        offers[d].append(t-1)\n\n    low = total_transaction\n    high = low * 2\n    ans = high\n    while low <= high:\n        mid = (low + high) // 2\n        if enough(mid):\n            ans = mid\n            high = mid - 1\n        else:\n            low = mid + 1\n    write(ans)\n\n\nmain()\n", "passed": true, "time": 0.24, "memory": 14372.0, "status": "done"}, {"code": "import sys\nimport bisect\nimport copy\ninput = sys.stdin.readline\n\nn,m=list(map(int,input().split()))\nK=[0]+list(map(int,input().split()))\nSP=[list(map(int,input().split())) for i in range(m)]\n\nSP2=[[] for i in range(n+1)]\n\nfor d,t in SP:\n    SP2[t].append(d)\n\nfor i in range(n+1):\n    SP2[i].sort()\n\nSUM=sum(K)\nMIN=SUM\nMAX=SUM*2\nMAXBUY=0\n\nfor day in range(MIN,MAX+1):\n\n    DAYS=[[] for i in range(day+1)]\n\n    for i in range(n+1):\n        x=bisect.bisect_right(SP2[i],day)-1\n        if x>=0:\n            DAYS[SP2[i][x]].append(i)\n\n    GOLD=0\n    SUMK=SUM\n    K2=copy.deepcopy(K)\n\n    for d in range(1,day+1):\n        GOLD+=1\n\n        for t in DAYS[d]:\n            DBUY=min(K2[t],GOLD,SUMK)\n            K2[t]-=DBUY\n            GOLD-=DBUY\n\n\n    if GOLD>=sum(K2)*2:\n        print(day)\n        break\n\n\n\n\n        \n        \n", "passed": true, "time": 0.24, "memory": 14316.0, "status": "done"}, {"code": "import sys\nimport bisect\nimport copy\ninput = sys.stdin.readline\n\nn,m=list(map(int,input().split()))\nK=[0]+list(map(int,input().split()))\nSP=[list(map(int,input().split())) for i in range(m)]\n\nSP2=[[] for i in range(n+1)]\n\nfor d,t in SP:\n    SP2[t].append(d)\n\nfor i in range(n+1):\n    SP2[i].sort()\n\nSUM=sum(K)\nMIN=SUM\nMAX=SUM*2\nMAXBUY=0\n\nwhile MIN!=MAX:\n    day=(MIN+MAX)//2\n\n    DAYS=[[] for i in range(day+1)]\n\n    for i in range(n+1):\n        x=bisect.bisect_right(SP2[i],day)-1\n        if x>=0:\n            DAYS[SP2[i][x]].append(i)\n\n    GOLD=0\n    SUMK=SUM\n    K2=copy.deepcopy(K)\n\n    for d in range(1,day+1):\n        GOLD+=1\n\n        for t in DAYS[d]:\n            DBUY=min(K2[t],GOLD,SUMK)\n            K2[t]-=DBUY\n            GOLD-=DBUY\n\n\n    if GOLD>=sum(K2)*2:\n        MAX=day\n    else:\n        MIN=day+1\n\nprint(MIN)\n\n\n\n\n        \n        \n", "passed": true, "time": 0.15, "memory": 14252.0, "status": "done"}, {"code": "import math\nfrom collections import defaultdict\nimport sys\n#input = sys.stdin.readline\n\n\ndef main():\n    n, m = list(map(int, input().split()))\n    k = list(map(int, input().split()))\n    sales = [(0, 0)] * m\n    for i in range(m):\n        a, b = list(map(int, input().split()))\n        sales[i] = (b, a)\n\n    def check(days):\n        last_sale = {}\n        for sale in sales:\n            if sale[1] <= days:\n                if sale[0] not in last_sale or sale[1] > last_sale[sale[0]]:\n                    last_sale[sale[0]] = sale[1]\n\n        date_last_sales = {}\n        for t, d in list(last_sale.items()):\n            if d not in date_last_sales:\n                date_last_sales[d] = [t]\n            else:\n                date_last_sales[d].append(t)\n\n        balance = 0\n        required = [0] + k.copy()\n\n        end = 0\n        for d in range(1, days+1):\n            balance += 1\n            if d in date_last_sales:\n                for t in date_last_sales[d]:\n                    if required[t] > 0:\n                        if required[t] > balance:\n                            end += required[t] - balance\n                        balance -= min(required[t], balance)\n                        required[t] = 0\n            if d == days:  # last day\n                for r in required:\n                    if r > 0:\n                        end += r\n\n        return 2*end <= balance\n\n    total = sum(k)\n    for i in range(1, 2*total+1):\n        if check(i):\n            print(i)\n            break\n\n\ndef __starting_point():\n    main()\n\n__starting_point()", "passed": true, "time": 0.14, "memory": 14160.0, "status": "done"}, {"code": "import sys\n\nDEBUG = False\n\nif DEBUG:\n    inf = open(\"input.txt\")\nelse:\n    inf = sys.stdin\n\nN, M = list(map(int, inf.readline().split(' ')))\nn_items = list(map(int, inf.readline().split(' ')))\nsales = []\nfor _ in range(M):\n    sale = list(map(int, inf.readline().split(' ')))\n    sales.append(sale)\n\nsales = sorted(sales, key=lambda x: x[0])\n\n# print(N, M)\n# print(n_items)\n# print(sales)\n# last_sales = [0 for _ in range(N)] # last sale day\nlast_sales = {k: -1 for k in range(N+1)} # for convenience ...\nfinal_sol = 99999999\n\nfor i in range(M):\n    sale_day, sale_type = sales[i]\n    last_sales[sale_type] = sale_day\n    if i != M-1: # not last sale\n        if sales[i+1][0] == sale_day: # same sale day\n            continue\n    \n    total = 0\n    lasts = last_sales.items()\n    lasts = sorted(lasts, key=lambda x: x[1]) # sort by day\n    burle = 0\n    before_lastday = -1\n    for stype, last_sday in lasts:\n        if stype == 0:\n            continue\n        if last_sday == -1:\n            # non-sale item\n            total += n_items[stype-1]*2\n            continue\n        \n        if before_lastday == -1:\n            burle = last_sday\n        else:\n            burle += last_sday - before_lastday\n        before_lastday = last_sday\n\n        bought = min(burle, n_items[stype-1])\n        left = n_items[stype-1] - bought\n        burle -= bought\n        total += bought + 2*left\n    \n    # print(sale_day, total)\n    sol = max(sale_day, total)\n    if final_sol > sol:\n        final_sol = sol\n\nprint(final_sol)", "passed": true, "time": 0.14, "memory": 14096.0, "status": "done"}, {"code": "import sys\n\nDEBUG = False\n\nif DEBUG:\n    inf = open(\"input.txt\")\nelse:\n    inf = sys.stdin\n\nN, M = list(map(int, inf.readline().split(' ')))\nn_items = list(map(int, inf.readline().split(' ')))\nsales = []\nfor _ in range(M):\n    sale = list(map(int, inf.readline().split(' ')))\n    sales.append(sale)\n\nsales = sorted(sales, key=lambda x: x[0])\n\n# print(N, M)\n# print(n_items)\n# print(sales)\n# last_sales = [0 for _ in range(N)] # last sale day\nlast_sales = {k: -1 for k in range(N+1)} # for convenience ...\nfinal_sol = 99999999\n\nfor i in range(M):\n    sale_day, sale_type = sales[i]\n    last_sales[sale_type] = sale_day\n    if i != M-1: # not last sale\n        if sales[i+1][0] == sale_day: # same sale day\n            continue\n    \n    total = 0\n    lasts = last_sales.items()\n    lasts = sorted(lasts, key=lambda x: x[1]) # sort by day\n    burle = 0\n    before_lastday = -1\n    for stype, last_sday in lasts:\n        if stype == 0:\n            continue\n        if last_sday == -1:\n            # non-sale item\n            total += n_items[stype-1]*2\n            continue\n        \n        if before_lastday == -1:\n            burle = last_sday\n        else:\n            burle += last_sday - before_lastday\n        before_lastday = last_sday\n\n        bought = min(burle, n_items[stype-1])\n        left = n_items[stype-1] - bought\n        burle -= bought\n        total += bought + 2*left\n    \n    # print(sale_day, total)\n    sol = max(sale_day, total)\n    if final_sol > sol:\n        final_sol = sol\n\nprint(final_sol)", "passed": true, "time": 0.15, "memory": 14120.0, "status": "done"}, {"code": "import sys\nimport copy\n\nDEBUG = False\n\nif DEBUG:\n    inf = open(\"input.txt\")\nelse:\n    inf = sys.stdin\n\nN, M = list(map(int, inf.readline().split(' ')))\nn_items = list(map(int, inf.readline().split(' ')))\nsales = []\nfor _ in range(M):\n    sale = list(map(int, inf.readline().split(' ')))\n    sales.append(sale) # sale_day, sale_type\n\nsales = sorted(sales, key=lambda x: x[0], reverse=True) # sort by day\n\ndef can_buy_in(dday):\n    used = 0\n    money_left = dday\n    items = copy.deepcopy(n_items)\n    for sale_day, sale_type in sales:\n        if sale_day > dday:\n            continue\n        \n        if money_left > sale_day:\n            money_left = sale_day\n        can_buy = min(items[sale_type-1], money_left)\n        # buy it\n        used += can_buy\n        items[sale_type-1] -= can_buy\n        money_left -= can_buy\n\n        if money_left == 0:\n            break\n    \n    need_money_for_rest = sum(items) * 2\n    return need_money_for_rest + used <= dday\n\ntotal_items = sum(n_items)\nlow = total_items\nhigh = total_items * 2\n\n# find minimum can_buy day\nwhile low <= high:\n    mid = (low + high) // 2\n    if can_buy_in(mid):\n        high = mid-1\n    else:\n        low = mid+1\n\nprint(low)", "passed": true, "time": 0.15, "memory": 14296.0, "status": "done"}, {"code": "n, m = input().split()\nn = int(n)\nm = int(m)\nnList = input().split()\nbList = [0] * len(nList)\nfor i in range(len(nList)):\n    nList[i] = int(nList[i])\nshopD = {}\nshopT = {}\noHis = []\nmHis = []\nmaxD = 0\nfor i in range(m):\n    d, t = input().split()\n    if nList[int(t) - 1] != 0:\n        maxD = max(maxD, int(d))\n        if d not in shopD.keys():\n            shopD.update({d: [int(t)]})\n        else:\n            if int(t) not in shopD[d]:\n                shopD[d].append(int(t))\n        if t not in shopT.keys():\n            shopT.update({t: [int(d)]})\n        else:\n            if int(d) not in shopT[t]:\n                shopT[t].append(int(d))\nfor i, j in shopT.items():\n    j = list(dict.fromkeys(j))\n    j.sort()\n    shopT[i] = j\nfor i, j in shopD.items():\n    j = list(dict.fromkeys(j))\n    shopD[i] = j\ntotal = sum(nList)\ncoin = 0\nday = 0\ndef modifyMis(t, left):\n    if left == 0:\n        for ii in range(len(mHis))[::-1]:\n            if mHis[ii]['t'] == t:\n                mHis.pop(ii)\n    else:\n        for ii in range(len(mHis))[::-1]:\n            if mHis[ii]['t'] == t:\n                mHis[ii]['n'] = left\nwhile total > 0 and day < maxD:\n    coin += 1\n    day += 1\n    oHis.append({'t': [], 'n': []})\n    if str(day) in shopD.keys():\n        for t in shopD[str(day)]:\n            if nList[t - 1] > 0:\n                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:\n                    i = 0\n                    j = 0\n                    while shopT[str(t)][i] < day:\n                        extraC = 0\n                        d = shopT[str(t)][i]\n                        if t in oHis[d - 1]['t']:\n                            indexT = oHis[d - 1]['t'].index(t)\n                            extraC += oHis[d - 1]['n'][indexT]\n                            bList[t - 1] -= oHis[d - 1]['n'][indexT]\n                            total += oHis[d - 1]['n'][indexT]\n                            oHis[d - 1]['t'].pop(indexT)\n                            oHis[d - 1]['n'].pop(indexT)\n                        while j < len(mHis) and mHis[j]['d'] < d:\n                            j += 1\n                        while extraC > 0 and len(mHis) > j:\n                            thisT = mHis[j]['t']\n                            thisD = mHis[j]['d']\n                            change = min(extraC, mHis[j]['n'])\n                            bList[thisT - 1] += change\n                            total -= change\n                            extraC -= change\n                            mHis[j]['n'] -= change\n                            modifyMis(thisT, nList[thisT - 1] - bList[thisT - 1])\n                            if thisT in oHis[thisD - 1]['t']:\n                                oHis[thisD - 1]['n'][oHis[thisD - 1]['t'].index(thisT)] += change\n                            else:\n                                oHis[thisD - 1]['t'].append(thisT)\n                                oHis[thisD - 1]['n'].append(change)\n                        i += 1\n                        coin += extraC\n            buy = min(nList[t - 1] - bList[t - 1], coin)\n            if buy != 0:\n                oHis[day - 1]['t'].append(t)\n                oHis[day - 1]['n'].append(buy)\n                total -= buy\n                bList[t - 1] += buy\n                modifyMis(t, nList[t - 1] - bList[t - 1])  \n                coin -= buy\n            if nList[t - 1] - bList[t - 1] > 0:\n                mHis.append({'d': day, 't': t, 'n': nList[t - 1] - bList[t - 1]}) \n    if coin >= total * 2:\n        break\nday += max(total * 2 - coin, 0)\nprint(day)", "passed": true, "time": 0.69, "memory": 14408.0, "status": "done"}, {"code": "n, m = input().split()\nn = int(n)\nm = int(m)\nnList = input().split()\nbList = [0] * len(nList)\nfor i in range(len(nList)):\n    nList[i] = int(nList[i])\nshopD = {}\nshopT = {}\noHis = []\nmHis = []\nmaxD = 0\nfor i in range(m):\n    d, t = input().split()\n    if nList[int(t) - 1] != 0:\n        maxD = max(maxD, int(d))\n        if d not in list(shopD.keys()):\n            shopD.update({d: [int(t)]})\n        else:\n            if int(t) not in shopD[d]:\n                shopD[d].append(int(t))\n        if t not in list(shopT.keys()):\n            shopT.update({t: [int(d)]})\n        else:\n            if int(d) not in shopT[t]:\n                shopT[t].append(int(d))\nfor i, j in list(shopT.items()):\n    j = list(dict.fromkeys(j))\n    j.sort()\n    shopT[i] = j\nfor i, j in list(shopD.items()):\n    j = list(dict.fromkeys(j))\n    shopD[i] = j\ntotal = sum(nList)\ncoin = 0\nday = 0\ndef modifyMis(t, left):\n    if left == 0:\n        for ii in range(len(mHis))[::-1]:\n            if mHis[ii]['t'] == t:\n                mHis.pop(ii)\n    else:\n        for ii in range(len(mHis))[::-1]:\n            if mHis[ii]['t'] == t:\n                mHis[ii]['n'] = left\nwhile total > 0 and day < maxD:\n    coin += 1\n    day += 1\n    oHis.append({'t': [], 'n': []})\n    if str(day) in list(shopD.keys()):\n        for t in shopD[str(day)]:\n            if nList[t - 1] > 0:\n                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:\n                    i = 0\n                    j = 0\n                    while shopT[str(t)][i] < day:\n                        extraC = 0\n                        d = shopT[str(t)][i]\n                        if t in oHis[d - 1]['t']:\n                            indexT = oHis[d - 1]['t'].index(t)\n                            extraC += oHis[d - 1]['n'][indexT]\n                            bList[t - 1] -= oHis[d - 1]['n'][indexT]\n                            total += oHis[d - 1]['n'][indexT]\n                            oHis[d - 1]['t'].pop(indexT)\n                            oHis[d - 1]['n'].pop(indexT)\n                        while j < len(mHis) and mHis[j]['d'] < d:\n                            j += 1\n                        while extraC > 0 and len(mHis) > j:\n                            thisT = mHis[j]['t']\n                            thisD = mHis[j]['d']\n                            change = min(extraC, mHis[j]['n'])\n                            bList[thisT - 1] += change\n                            total -= change\n                            extraC -= change\n                            mHis[j]['n'] -= change\n                            modifyMis(thisT, nList[thisT - 1] - bList[thisT - 1])\n                            if thisT in oHis[thisD - 1]['t']:\n                                oHis[thisD - 1]['n'][oHis[thisD - 1]['t'].index(thisT)] += change\n                            else:\n                                oHis[thisD - 1]['t'].append(thisT)\n                                oHis[thisD - 1]['n'].append(change)\n                        i += 1\n                        coin += extraC\n            buy = min(nList[t - 1] - bList[t - 1], coin)\n            if buy != 0:\n                oHis[day - 1]['t'].append(t)\n                oHis[day - 1]['n'].append(buy)\n                total -= buy\n                bList[t - 1] += buy\n                modifyMis(t, nList[t - 1] - bList[t - 1])  \n                coin -= buy\n            if nList[t - 1] - bList[t - 1] > 0:\n                mHis.append({'d': day, 't': t, 'n': nList[t - 1] - bList[t - 1]}) \n    if coin >= total * 2:\n        break\nday += max(total * 2 - coin, 0)\nprint(day)\n", "passed": true, "time": 0.14, "memory": 14520.0, "status": "done"}, {"code": "#binary search reconstructure\n  \n\ndef BinarySearch(my_list,key):\n    l = 0\n    r = len(my_list)- 1 \n    #print(l,r)\n    while r > l :\n        mid = (l+r)//2\n        if my_list[mid+1] <= key :\n            l = mid + 1  \n        else :\n            r = mid   \n        #print(l,r)\n    return l\n\ndef weather_can_buy(day,total,req_list,sale_days):\n    tmp_buy = []\n    last_day = []\n    # money = day\n    # bug anything that is on sale\n    d = day\n    my_total = total\n    for i in range(len(req_list)) : \n        last_day.append(0)\n    for i in range(d):\n        tmp_buy.append(0)    \n    for i in range(len(sale_days)) : \n        if len(sale_days[i]) > 0 : \n            index = BinarySearch(sale_days[i],day)\n            last_day[i] = sale_days[i][index]\n    for i in range(len(last_day)) :\n        if last_day[i]-1 > -1 :\n            tmp_buy[last_day[i]-1] += req_list[i]\n    # buying\n    money = 0\n    for i in range(d):\n        money += 1\n        my_total -= min(money,tmp_buy[i])\n        money -= min(money,tmp_buy[i])        \n    if my_total < 0 :\n        return True\n    elif money >= my_total * 2:\n        return True\n    else :\n        return False\n    \ndef function():\n    tmp = input().split(\" \")\n    n = int(tmp[0]) # The number of type\n    m = int(tmp[1]) \n    req_list = input().split(\" \")\n    req_list = list(map(int,req_list)) \n    total = sum(req_list)\n    sale_days = []\n    # sale days for acceleration\n    for i in range(len(req_list)):\n        sale_days.append([0])  \n    for i in range(m) :\n        tmp = input().split(\" \")\n        dj,tj = (int(tmp[0]),int(tmp[1]))\n        sale_days[tj-1].append(dj)\n    for i in range(len(sale_days)) :\n        sale_days[i] = sorted(sale_days[i])\n    # optimized by sorting\n    for i in range(len(sale_days)) :\n        sale_days[i] = sorted(sale_days[i])     \n    #day = 0\n\n    l = 1\n    r = 2*total\n    while r > l :\n        mid = (l+r)//2\n        if weather_can_buy(mid,total,req_list,sale_days) :\n            r = mid\n        else :\n            l = mid + 1 \n    print(r)\n    \nfunction()\n", "passed": true, "time": 0.14, "memory": 14248.0, "status": "done"}, {"code": "import copy\nfrom collections import defaultdict\n\nBIG = 10**9\nN, M = [int(i) for i in input().split()]\n\nK = [0] + [int(i) for i in input().split()]\n\nsumK = sum(K)\nmax_days = 2*sum(K)\n\nday_at_sale_per_item = defaultdict(list)\nfor i in range(M):\n    day, item = [int(i) for i in input().split()]\n    day_at_sale_per_item[item].append(day)\n\nsales_per_day = defaultdict(list)\nfor item, days in list(day_at_sale_per_item.items()):\n    for day in days:\n        sales_per_day[day].append(item)\n\nL, R = 0, max_days\nanswer = 0\nwhile L <= R:\n    m = (L+R)//2\n\n    def get_best_sales(m):\n        best_sales = defaultdict(list)\n        for item, days in list(day_at_sale_per_item.items()):\n            best_day = 0\n            for day in days:\n                if day <= m:\n                    best_day = max(best_day, day)\n            if best_day:\n                best_sales[best_day].append(item)\n        return best_sales\n\n    def available_sales(m):\n        available_money = 0\n        nb_sales = 0\n        cK = copy.deepcopy(K)\n\n        best_sales = get_best_sales(m)\n\n        for day in range(1, m+1):\n            available_money += 1\n            for item in best_sales[day]:\n                buy = min(cK[item], available_money)\n                if buy:\n                    cK[item] -= buy\n                    available_money -= buy\n                    nb_sales += buy\n        return nb_sales\n\n    def possible(m):\n        total_money = m\n        needed_money = 2 * sumK - available_sales(m)\n        return total_money >= needed_money\n\n    if possible(m):\n        answer = m\n        R = m-1\n    else:\n        L = m+1\nprint(answer)\n", "passed": true, "time": 0.14, "memory": 14164.0, "status": "done"}, {"code": "from collections import defaultdict\n\ndef possible(days):\n    nonlocal events, k\n    \n    latest_ev = defaultdict(int)\n    for d, t in events:\n        if d <= days:\n            latest_ev[t] = max(latest_ev[t], d)\n    \n    earned = days\n    offers_needed = 2 * sum(k) - earned\n\n    offers = 0    \n    cur_day = 0\n    cur_val = 0\n    for t, d in sorted(list(latest_ev.items()), key=lambda x: x[1]):\n        cur_val += d - cur_day\n        cur_day = d\n        offers_to_take = min(k[t], cur_val)\n        offers += offers_to_take\n        cur_val -= offers_to_take\n    return offers >= offers_needed\n    \n\nn, m = list(map(int, input().split()))\n\nk = list(map(int, input().split()))\n\nevents = []\nfor _ in range(m):\n    d, t = list(map(int, input().split()))\n    t -= 1\n    events.append((d, t))\n    \nlo = 0\nhi = 4*10**5\n\nwhile lo + 1 < hi:\n    mid = (lo+hi)//2\n    \n    if possible(mid):\n        hi = mid\n    else:\n        lo = mid\n    \nprint(hi)\n", "passed": true, "time": 0.14, "memory": 14360.0, "status": "done"}, {"code": "from collections import defaultdict\n\ndef possible(days):\n    nonlocal events, k\n    \n    latest_ev = defaultdict(int)\n    for d, t in events:\n        if d <= days:\n            latest_ev[t] = max(latest_ev[t], d)\n    \n    earned = days\n    offers_needed = 2 * sum(k) - earned\n\n    offers = 0    \n    cur_day = 0\n    cur_val = 0\n    for t, d in sorted(list(latest_ev.items()), key=lambda x: x[1]):\n        cur_val += d - cur_day\n        cur_day = d\n        offers_to_take = min(k[t], cur_val)\n        offers += offers_to_take\n        cur_val -= offers_to_take\n        if offers >= offers_needed:\n            return True\n    return offers >= offers_needed\n    \n\nn, m = list(map(int, input().split()))\n\nk = list(map(int, input().split()))\n\nevents = []\nfor _ in range(m):\n    d, t = list(map(int, input().split()))\n    t -= 1\n    events.append((d, t))\n    \nlo = sum(k) - 1\nhi = 2 * sum(k)\n\nwhile lo + 1 < hi:\n    mid = (lo+hi)//2\n    \n    if possible(mid):\n        hi = mid\n    else:\n        lo = mid\n    \nprint(hi)\n", "passed": true, "time": 0.14, "memory": 14168.0, "status": "done"}, {"code": "def check(mid):\n\tl = [0 for i in range(n)]\n\tfor i in b:\n\t\tif(i[0] > mid): break\n\t\tl[i[1]-1] = i[0]\n\tv = [0 for i in range(mid+1)]\n\tfor i in range(n):\n\t\tv[l[i]] += a[i]\n\tct = 0\n\tfor i in range(1,mid+1):\n\t\tct += 1\n\t\tif(ct >= v[i]):\n\t\t\tct -= v[i]\n\t\t\tv[i] = 0\n\t\telse:\n\t\t\tv[i] -= ct\n\t\t\tct = 0\n\treturn ct >= 2*sum(v)\n\ndef bs():\n\tl = 0\n\tr = 5*10**5\n\twhile(l <= r):\n\t\tmid = (l+r)//2\n\t\tif(check(mid)):\n\t\t\tr = mid-1\n\t\telse:\n\t\t\tl = mid+1\n\treturn r+1\n\nn,m = map(int,input().split())\na = list(map(int,input().split()))\nb = []\nfor i in range(m):\n\tb.append(list(map(int,input().split())))\nb.sort()\nprint(bs())", "passed": true, "time": 0.52, "memory": 15516.0, "status": "done"}, {"code": "import sys\ninput = sys.stdin.readline\ndef check(num):\n\tlast = [0 for i in range(n)]\n\tfor i in o:\n\t\tif i[0]>num:\n\t\t\tbreak\n\t\telse:\n\t\t\tlast[i[1]-1] = i[0]\n\tb = [0 for i in range(num+1)]\n\tfor i in range(n):\n\t\tb[last[i]] += a[i]\n\n\ti = 0\n\tc = 0\n\td = 0\n\tfor i in range(1,num+1):\n\t\tc += 1\n\t\tif(c >= b[i]):\n\t\t\tc -= b[i]\n\t\t\tb[i] = 0\n\t\telse:\n\t\t\tb[i] -= c\n\t\t\tc = 0\n\n\ts = sum(b)\n\tif s*2<=c:\n\t\treturn True\n\treturn False\n\n\n\nn,m = map(int,input().split())\na = list(map(int,input().split()))\no = []\nfor i in range(m):\n\tx,y = map(int,input().split())\n\to.append((x,y))\no.sort()\nlow = 1\nhigh = sum(a)*2\nwhile low<high:\n\tmid = (low+high)//2\n\tif check(mid):\n\t\thigh = mid - 1\n\telse:\n\t\tlow = mid + 1\nif check(low):\n\tprint (low)\nelse:\n\tprint (low+1)", "passed": true, "time": 0.14, "memory": 14316.0, "status": "done"}, {"code": "def check(x):\n    last=[0]*(n+1)\n    for i in tmp:\n        if i[0]>x:\n            break\n        else:\n            last[i[1]]=i[0]\n    sal=[0]*(x+1)\n    for i in range(1,n+1):\n        sal[last[i]]+=lis[i-1]\n    c=0\n    for i in range(1,x+1):\n        c+=1\n        if sal[i]>=c:\n            sal[i]-=c\n            c=0\n        else:\n            c-=sal[i]\n            sal[i]=0\n    if sum(sal)*2<=c:\n        return True\n    else:\n        return False        \nn,m = list(map(int,input().split()))\nlis = list(map(int,input().split()))\ntmp=[]\nfor _ in range(m):\n    a,b = list(map(int,input().split()))\n    tmp.append([a,b])\ntmp.sort()\nl=0\nr=sum(lis)*2\nwhile l<=r:\n    mid = l + (r-l)//2\n    if check(mid):\n        r = mid-1\n    else:\n        l = mid+1\nif check(r):\n    print(r)\nelif check(l):\n    print(l)\nelse:\n    print(l+1)    \n\n\n\n", "passed": true, "time": 0.14, "memory": 14168.0, "status": "done"}, {"code": "from collections import deque\n\n\ndef main():\n    n, m = list(map(int, input().split()))\n    wanted_cnt = list(map(int, input().split()))\n    Order = [tuple(map(int, input().split())) for i in range(m)]\n    #count the maximum number which you can buy on sales day.\n    S = sum(wanted_cnt)\n\n    def ispossible_within(Day):\n        sale_get_cnt = 0\n        last_sale = [0]*n\n        for day, good in Order:\n            if day > Day:\n                continue\n            last_sale[good-1] = max(last_sale[good-1], day)\n        Que = []\n        for i in range(n):\n            if wanted_cnt[i] > 0 and last_sale[i] > 0:\n                Que.append((last_sale[i], wanted_cnt[i]))\n        Que.sort()\n        que = deque(Que)\n        while que:\n            sale_day, wanted = que.popleft()\n            money_left = sale_day - sale_get_cnt\n            if money_left >= wanted:\n                sale_get_cnt += wanted\n            elif money_left < wanted:\n                sale_get_cnt += money_left\n        left_money = Day - sale_get_cnt\n        left = S - sale_get_cnt\n\n        return left_money >= 2*left\n\n    impossible = 0\n    possible = 2020\n    while possible - impossible > 1:\n        m = (impossible + possible)//2\n        if ispossible_within(m):\n            possible = m\n        else:\n            impossible = m\n    print(possible)\n    return\n\n\ndef __starting_point():\n    main()\n\n\n__starting_point()", "passed": true, "time": 0.14, "memory": 14304.0, "status": "done"}]