Microtransactions (hard version)

题意翻译

# **题目描述** 有n种物品，对于第i个物品，你需要买ki个，每个物品在非打折日买是2块钱，在打折日买是1块钱，每天你可以赚1块钱，一共有m个打折日，在第di天第ti种物品打折，最少需要多少天可以买完你需要的物品 # **输入格式** 第一行包含两个整数n和m（1≤n，m≤2e5）中的商品类型数和打折的天数。 输入的第二行包含n个整数ki，其中ki是第i类需要的个数。（0≤Σki≤2e5）。 接下来的m行，每行两个数di，ti）（1≤di≤2e5，1≤ti≤n）表示第ti个商品在di天打特价 # **输出格式** 一个整数，表示最早在哪一天能买完所有需要的商品

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #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