CF1165F2 Microtransactions (hard version)

有 $n$ 种物品，对于第 $i$ $(1\le i \le n)$ 个物品，你需要买 $k_i$ 个（你每次购物是在**晚上**），每个物品在非打折日买是 $2$ 块钱，在打折日买是 $1$ 块钱，每天**早上**你可以赚 $1$ 块钱，一共有 $m$ 个打折日，在第 $d_i$ 天第 $t_i$ 种物品打折，问最少需要多少天可以买完你需要的物品。注意，你每天可以买任意多数量以及种类的商品（只要你有足够的余额）。

第一行包含两个整数 $n$ 和 $m$ $(1\le n,m \le 2\times 10^5)$ 中的商品类型数和打折的天数。 输入的第二行包含 $n$ 个整数 $k_i$，其中 $k_i$ 是第 $i$ 类需要的个数。$(0 \le \sum k_i \le 2\times 10^5)$。 接下来的 $m$ 行，每行两个数 $(d_i,t_i$) $(1 \le d_i \le 2\times 10^5, 1 \le t_i \le n)$，表示第 $t_i$ 个商品在 $d_i$ 天打特价。

一个整数，表示最早在哪一天能买完所有需要的商品。