#include #include #include #include #include #include #include #include #include #include #include #include #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; int n, m; ll a[100005]; int x[100005]; ll w[100005]; void input(){ cin >> n >> m; for(int i = 0; i < n; i++){ cin >> a[i]; } for(int i = 0; i < m; i++){ cin >> x[i] >> w[i]; x[i]--; } } const ll INF = 1e18; bool judge(ll c){ if(c == 0){ ll w_sum = 0; for(int i = 0; i < m; i++) w_sum += w[i]; for(int i = 0; i < n; i++) { if(a[i] <= w_sum) return false; } return true; } vector d_load(n+1), load(n+1); auto add_d_load = [&](int l, int r, ll d){ assert(l >= 0); chmin(r, n); // cout << l << ' ' << r << ' ' << d << endl; if(l < n)d_load[l] += d; if(r <=n) d_load[r] -= d; }; auto add_val = [&](int i, ll x){ assert(i >= 0); assert(i < n); if(i == 0){ load[0] += x; d_load[0] -= x; d_load[1] += x; }else{ d_load[i-1] += x; d_load[i] -= 2*x; d_load[i+1] += x; } }; for(int j = 0; j < m; j++){ if(w[j] < c){ // cout << 'H' << ' ' << x[j] << ' ' << w[j] << endl; add_val(x[j], w[j]); continue; } int l = x[j]-w[j]/c; if(l <= 0){ // add_val(0, w[j]%c-c*l); load[0] += w[j]%c-c*l; l = 0; }else{ add_d_load(l-1, l, w[j]%c); } add_d_load(x[j]+w[j]/c, x[j]+w[j]/c+1, -(w[j]%c)); // cout << l << ' ' << w[j] << endl; add_d_load(l, x[j], c); add_d_load(x[j], x[j]+w[j]/c, -c); } for(int i = 0; i < n; i++) d_load[i+1] += d_load[i]; for(int i = 0; i < n; i++) load[i+1] += load[i]+d_load[i]; for(int i = 0; i < n; i++){ // cout << load[i] << ' ' << a[i] << endl; if(load[i] >= a[i]) return false; } // debug_value(c); return true; } void solve(){ if(judge(0)){ cout << 0 << endl; return; }else if(!judge(INF)){ cout << -1 << endl; return; } ll l = 0, r = INF; while(r-l > 1){ ll c = (l+r)/2; // debug_value(c); if(judge(c)) r = c; else l = c; } cout << r << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; input(); solve(); }