题目来源：

F1：https://codeforces.com/contest/1165/problem/F1

F2：https://codeforces.com/contest/1165/problem/F2

题意：AA现在有n种装备要买，每个装备要买ki个，每一天的早上AA会赚到1元钱，每个装备的价钱都是2元，但是现在有m个特价活动（d1,ti）意思是在di天的时候第ti个装备只要1元钱，问你买完所有的装备所需的最小天数是多少？
F1 和 F2的题是一样的，只是数据范围不一样，我用的方法都是二分（logn的时间复杂度）所以两个题的代码是一样的，都可以过。

思路：
其实这个是一道二分题，和之前做的一个题晾衣服的题好像差不多，奈何我还是不太会最后为了假装ak过cf然后就py了网友代码，谁知道这一py直接就rank1了QAQ。

每张碟的价格都是一样的，那么普通价格的不管我在什么时候买都是一样的，所以可以默认全部都在最后一天买。在考虑打折的碟。如果某张碟子打了多次折，那么我可以留到最后一次打折再买。然后就可以二分了，check的时候从mid天往前倒着推，遇到打折的就直接买够，最后判断一下不打折的就可以了，这里像贪心。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define PII pair<int,int>
#define PB push_back
#define POP pop_back
#define FI first
#define SE second
#define endl '\n'
#define ls x<<1
#define rs x<<1|1
const LL N=4e5+7,mod=998244353,INF=1e9;
int n,m;
int a[N],b[N];
vector<int>v[N];
int check(int x,int y){
    int re=x,cnt=0;
    int flag=0;
    for(int i=1;i<=n;i++)b[i]=a[i];
    for(int i=x;i>=1;i--){
            //cout<<i<<' '<<re<<endl;
        for(int j=0;j<v[i].size();j++){
            while(b[v[i][j]]&&re){
                re--;
                y--;
                b[v[i][j]]--;
            }
        }
        if(re>=i)re--,flag++;
    }
    return flag/2>=y;
}
int main()
{
    cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        cnt+=a[i];
    }
    int x,y;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        v[x].PB(y);
    }
    int ans=INF;
    int l=cnt,r=2*cnt;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid,cnt)){
            ans=min(ans,mid);
            r=mid-1;
        }
        else l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}