#include #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; using lint=long long; int main(){ int n,m; scanf("%d%d",&n,&m); vector a(n); rep(i,n) scanf("%lld",&a[i]); vector x(m); vector w(m); rep(j,m) scanf("%d%lld",&x[j],&w[j]), x[j]--; { vector tmp(n); rep(j,m) tmp[x[j]]+=w[j]; x.clear(); w.clear(); rep(i,n) if(tmp[i]>0) { x.emplace_back(i); w.emplace_back(tmp[i]); } m=x.size(); /* vector> p(m); rep(j,m) p[j]={x[j],w[j]}; sort(p.begin(),p.end()); rep(j,m) tie(x[j],w[j])=p[j]; for(int j=m-2;j>=0;j--) if(x[j]==x[j+1]) { w[j]+=w[j+1]; w[j+1]=0; } rep(j,m) if(w[j]==0) { swap(x[j],x[m-1]); swap(w[j],w[m-1]); j--; m--; } x.resize(m); w.resize(m); */ } rep(j,m) if(w[j]>=a[x[j]]) return puts("-1"),0; if(accumulate(w.begin(),w.end(),0LL)<*min_element(a.begin(),a.end())) return puts("0"),0; const int OFFSET=2e5; vector sum(n+2*OFFSET+1); int lo=0,hi=1e5; while(hi-lo>1){ int mi=(lo+hi)/2; int c=mi; fill(sum.begin(),sum.end(),0LL); rep(j,m){ // left sum[x[j]-w[j]/c+OFFSET]+=c; sum[x[j]+OFFSET]-=c; sum[x[j]-w[j]/c+OFFSET-1]+=w[j]%c; sum[x[j]-w[j]/c+OFFSET]-=w[j]%c; // right sum[x[j]+OFFSET]-=c; sum[x[j]+w[j]/c+OFFSET]+=c; sum[x[j]+w[j]/c+OFFSET]-=w[j]%c; sum[x[j]+w[j]/c+OFFSET+1]+=w[j]%c; } rep(_,2) rep(i,(int)sum.size()-1) sum[i+1]+=sum[i]; bool ok=true; rep(i,n) if(sum[i+OFFSET]>=a[i]) { ok=false; break; } if(ok) hi=mi; else lo=mi; } printf("%d\n",hi); return 0; }