CF1165F2.Microtransactions (hard version)

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.

简单版本与困难版本的唯一区别在于约束条件。

伊万正在玩一款电脑游戏，游戏中包含一些微交易，用于让角色看起来更酷。由于伊万希望自己的角色真正酷炫，他打算购买其中一部分微交易——并且他不会开始玩游戏，直到他获得全部所需微交易为止。

每天（早晨），伊万恰好赚取 1 卢布（burle）。

游戏中共有 $n$ 种微交易。通常情况下，每种微交易价格为 2 卢布；若处于促销期，则价格为 1 卢布。伊万必须恰好订购第 $i$ 种微交易 $k_i$ 件（他在每天晚上进行订购）。

伊万可以在任意一天（当然前提是资金充足）订购任意数量（包括零）的任意种类微交易。若他想订购的微交易正处于促销期，则只需花费 1 卢布；否则需花费 2 卢布。

此外，游戏商店还提供 $m$ 个特殊优惠。第 $j$ 个优惠 $(d_j, t_j)$ 表示：在第 $d_j$ 天，第 $t_j$ 种微交易处于促销期。

伊万希望尽快完成所有微交易的订购。你的任务是计算他能够买齐所有所需微交易并真正开始游戏的最早天数。

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.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \cdot 10^5$），分别表示微交易类型的数量以及游戏商店中特价优惠的数量。

输入的第二行包含 $n$ 个整数 $k_1, k_2, \dots, k_n$（$0 \le k_i \le 2 \cdot 10^5$），其中 $k_i$ 表示 Ivan 需要订购的第 $i$ 种微交易的份数。保证所有 $k_i$ 的总和不小于 $1$，且不大于 $2 \cdot 10^5$。

接下来的 $m$ 行描述特价优惠。其中第 $j$ 行描述第 $j$ 个特价优惠，以一对整数 $(d_j, t_j)$（$1 \le d_j \le 2 \cdot 10^5,\ 1 \le t_j \le n$）给出，表示第 $t_j$ 种微交易在第 $d_j$ 天打折促销。

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

输出一个整数——伊万能够订购所有他想要的微交易并真正开始游戏的最早天数。