//#include #include "bits/stdc++.h" using namespace std; typedef long long ll; //#include "boost/multiprecision/cpp_int.hpp" //typedef boost::multiprecision::cpp_int ll; typedef long double dd; #define i_7 (ll)(1E9+7) //#define i_7 998244353 #define i_5 i_7-2 ll mod(ll a){ ll c=a%i_7; if(c>=0)return c; return c+i_7; } typedef pair l_l; typedef pair d_d; ll inf=(ll)1E16; #define rep(i,l,r) for(ll i=l;i<=r;i++) #define pb push_back ll max(ll a,ll b){if(ab)return b;else return a;} void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]); void Min(ll &pos,ll val){pos=min(pos,val);} void Add(ll &pos,ll val){pos=mod(pos+val);} dd EPS=1E-9; #define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define fi first #define se second /////////////////////////// #define N 100005 ll n,m; ll a[N]; ll x[N],w[N]; bool check(){ ll sum[n];memset(sum,0,sizeof(sum)); rep(i,0,m-1){ sum[x[i]]+=w[i]; } rep(i,0,n-1){ if(sum[i]>=a[i])return true; } return 0; } bool zerocheck(){ ll sum=0; rep(i,0,m-1)sum+=w[i]; rep(i,0,n-1){ if(sum>=a[i])return false; } return true; } int main(){fastio cin>>n>>m; rep(i,0,n-1)cin>>a[i]; rep(i,0,m-1){ cin>>x[i]>>w[i];x[i]--; } if(check()){ cout<<-1<1){ ll mid=(ok+ng)/2; ll imo[n],umo[n];memset(imo,0,sizeof(imo));memset(umo,0,sizeof(umo)); ll iml[n],uml[n];memset(iml,0,sizeof(iml));memset(uml,0,sizeof(uml)); rep(i,0,m-1){ if(x[i]+1<=n-1)imo[x[i]+1]-=mid; ll t=w[i]/mid; if(x[i]+1+t<=n-1)imo[x[i]+1+t]+=mid; if(x[i]+1+t<=n-1)umo[x[i]+1+t]+=mid*t; umo[x[i]]+=w[i]; if(x[i]+t+1<=n-1)umo[x[i]+t+1]-=w[i]; if(x[i]-1>=0)iml[x[i]-1]-=mid; t=w[i]/mid; if(x[i]-1-t>=0){ iml[x[i]-1-t]+=mid; uml[x[i]-1-t]+=mid*t; uml[x[i]-t-1]-=w[i]; } if(x[i]-1>=0)uml[x[i]-1]+=w[i]; } rep(i,1,n-1)imo[i]+=imo[i-1]; rep(i,0,n-1)umo[i]+=imo[i]; rep(i,1,n-1)umo[i]+=umo[i-1]; for(ll i=n-2;i>=0;i--)iml[i]+=iml[i+1]; for(ll i=n-1;i>=0;i--)uml[i]+=iml[i]; for(ll i=n-2;i>=0;i--)uml[i]+=uml[i+1]; ll sum[n];memset(sum,0,sizeof(sum)); rep(i,0,n-1)sum[i]=umo[i]+uml[i]; bool flag=true; rep(i,0,n-1){ if(sum[i]>=a[i]){flag=false;break;} } if(flag)ok=mid; else ng=mid; } cout<