← 返回题目列表

Codeforces · 1165/F2

F2. 微交易(硬版)

中文机器翻译题面 查看原题

简单版本和困难版本之间的唯一区别是限制。

Ivan 玩一款电脑游戏,其中包含一些微交易,以使角色看起来更酷。由于 Ivan 希望他的角色非常酷,因此他想使用其中一些微交易 - 并且在获得所有这些微交易之前他不会开始玩。

每天(早上)Ivan 正好挣 1 个 burle。

游戏中有 $$$n$$$ 种微交易类型。每次微交易通常花费 $$$2$$$ burle,如果打折则花费 $$$1$$$ burle。 Ivan 必须准确订购 $$$k_i$$$ 类型的 $$$i$$$ 微交易(他在晚上订购微交易)。

Ivan 可以在任何一天订购任意数量(可能为零)的任何类型的微交易(当然,如果他有足够的钱的话)。如果他想要订购的微交易正在促销,那么他可以以 $$$1$$$ burle 的价格购买,否则他可以以 $$$2$$$ burle 的价格购买。

游戏商店还有$$$m$$$特价优惠。第 $$$j$$$ 优惠 $$$(d_j, t_j)$$$ 表示第 $$$t_j$$$ 类型的微交易在第 $$$d_j$$$ 天进行销售。

Ivan 希望尽快订购所有微交易。您的任务是计算他可以购买他想要的所有微交易并实际开始玩游戏的最短日期。

输入

输入的第一行包含两个整数 $$$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$$$ 日出售。

输出

打印一个整数 — Ivan 可以订购他想要的所有微交易并实际开始玩游戏的最短日期。

示例

输入 #1

5 6
1 2 0 2 0
2 4
3 3
1 5
1 2
1 5
2 3

输出 #1

8

输入 #2

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

输出 #2

20