Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
F2. Microtransactions (hard version)

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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 2 \cdot 10^5$$$) — 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 2 \cdot 10^5$$$), 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 $$$2 \cdot 10^5$$$.

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 2 \cdot 10^5, 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

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/16/2022 07:43:37 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|