// #define _GLIBCXX_DEBUG #include // clang-format off std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os< template static constexpr bool tuple_like_v= false; template static constexpr bool tuple_like_v> = true; template static constexpr bool tuple_like_v> = true; template static constexpr bool tuple_like_v> = true; template auto to_tuple(const T &t) { if constexpr (tuple_like_v) return std::apply([](auto &&...x) { return std::make_tuple(x...); }, t); } template auto forward_tuple(const T &t) { if constexpr (tuple_like_v) return std::apply([](auto &&...x) { return std::forward_as_tuple(x...); }, t); } template static constexpr bool array_like_v= false; template static constexpr bool array_like_v> = true; template static constexpr bool array_like_v> = std::is_convertible_v; template static constexpr bool array_like_v> = true; template static constexpr bool array_like_v> = array_like_v> && std::is_convertible_v; template auto to_array(const T &t) { if constexpr (array_like_v) return std::apply([](auto &&...x) { return std::array{x...}; }, t); } template using to_tuple_t= decltype(to_tuple(T())); template using to_array_t= decltype(to_array(T())); template class SegmentTree_2D { public: using T= typename M::T; using Pos= std::array; std::vector xs; std::vector yxs; std::vector id, tol; std::vector val; template using canbe_Pos= std::is_convertible, std::tuple>; template using canbe_PosV= std::is_convertible, std::tuple>; template static constexpr bool canbe_Pos_and_T_v= std::conjunction_v, std::is_convertible>; int sz; inline int x2i(pos_t x) const { return std::lower_bound(xs.begin(), xs.end(), x) - xs.begin(); } inline int y2i(pos_t y) const { return std::lower_bound(yxs.begin(), yxs.end(), Pos{y, 0}, [](const Pos &a, const Pos &b) { return a[0] < b[0]; }) - yxs.begin(); } inline int xy2i(pos_t x, pos_t y) const { Pos p{y, x}; auto it= std::lower_bound(yxs.begin(), yxs.end(), p); return assert(p == *it), it - yxs.begin(); } template inline auto get_(const P &p) { if constexpr (z == 0) return std::get(p); else return std::get(p.first); } template inline void build(const XYW *xyw, int n, const T &v= M::ti()) { xs.resize(n), yxs.resize(n); for (int i= n; i--;) xs[i]= get_(xyw[i]); std::sort(xs.begin(), xs.end()), xs.erase(std::unique(xs.begin(), xs.end()), xs.end()), id.resize((sz= 1 << (32 - __builtin_clz(xs.size()))) * 2 + 1); std::vector ix(n), ord(n); for (int i= n; i--;) ix[i]= x2i(get_(xyw[i])); for (int i: ix) for (i+= sz; i; i>>= 1) ++id[i + 1]; for (int i= 1, e= sz * 2; i < e; ++i) id[i + 1]+= id[i]; val.assign(id.back() * 2, M::ti()), tol.resize(id[sz] + 1), std::iota(ord.begin(), ord.end(), 0), std::sort(ord.begin(), ord.end(), [&](int i, int j) { return get_(xyw[i]) == get_(xyw[j]) ? get_(xyw[i]) < get_(xyw[j]) : get_(xyw[i]) < get_(xyw[j]); }); for (int i= n; i--;) yxs[i]= {get_(xyw[ord[i]]), get_(xyw[ord[i]])}; std::vector ptr= id; for (int r: ord) for (int i= ix[r] + sz, j= -1; i; j= i, i>>= 1) { int p= ptr[i]++; if constexpr (z == 0) { if constexpr (std::tuple_size_v == 3) val[id[i + 1] + p]= std::get<2>(xyw[r]); else val[id[i + 1] + p]= v; } else val[id[i + 1] + p]= xyw[r].second; if (j != -1) tol[p + 1]= !(j & 1); } for (int i= 1, e= id[sz]; i < e; ++i) tol[i + 1]+= tol[i]; for (int i= 0, e= sz * 2; i < e; ++i) { auto dat= val.begin() + id[i] * 2; for (int j= id[i + 1] - id[i]; --j > 0;) dat[j]= M::op(dat[j * 2], dat[j * 2 + 1]); } } inline T fold(int i, int a, int b) const { int n= id[i + 1] - id[i]; T ret= M::ti(); auto dat= val.begin() + id[i] * 2; for (a+= n, b+= n; a < b; a>>= 1, b>>= 1) { if (a & 1) ret= M::op(ret, dat[a++]); if (b & 1) ret= M::op(dat[--b], ret); } return ret; } inline void seti(int i, int j, T v) { auto dat= val.begin() + id[i] * 2; for (dat[j+= id[i + 1] - id[i]]= v; j;) j>>= 1, dat[j]= M::op(dat[2 * j], dat[2 * j + 1]); } public: template , canbe_PosV

>>> SegmentTree_2D(const P *p, size_t n) { build<0>(p, n); } template , canbe_PosV

>>> SegmentTree_2D(const std::vector

&p): SegmentTree_2D(p.data(), p.size()) {} template ::value>> SegmentTree_2D(const std::set

&p): SegmentTree_2D(std::vector(p.begin(), p.end())) {} template >> SegmentTree_2D(const P *p, size_t n, const U &v) { build<0>(p, n, v); } template >> SegmentTree_2D(const std::vector

&p, const U &v): SegmentTree_2D(p.data(), p.size(), v) {} template >> SegmentTree_2D(const std::set

&p, const U &v): SegmentTree_2D(std::vector(p.begin(), p.end()), v) {} template >> SegmentTree_2D(const std::pair *p, size_t n) { build<1>(p, n); } template >> SegmentTree_2D(const std::vector> &p): SegmentTree_2D(p.data(), p.size()) {} template >> SegmentTree_2D(const std::map &p): SegmentTree_2D(std::vector(p.begin(), p.end())) {} // [l,r) x [u,d) T fold(pos_t l, pos_t r, pos_t u, pos_t d) const { T ret= M::ti(); int L= x2i(l), R= x2i(r); auto dfs= [&](auto &dfs, int i, int a, int b, int c, int d) -> void { if (c == d || R <= a || b <= L) return; if (L <= a && b <= R) return ret= M::op(ret, fold(i, c, d)), void(); int m= (a + b) / 2, ac= tol[id[i] + c] - tol[id[i]], bc= c - ac, ad= tol[id[i] + d] - tol[id[i]], bd= d - ad; dfs(dfs, i * 2, a, m, ac, ad), dfs(dfs, i * 2 + 1, m, b, bc, bd); }; return dfs(dfs, 1, 0, sz, y2i(u), y2i(d)), ret; } void set(pos_t x, pos_t y, T v) { for (int i= 1, p= xy2i(x, y);;) { if (seti(i, p - id[i], v); i >= sz) break; if (int lc= tol[p] - tol[id[i]], rc= (p - id[i]) - lc; tol[p + 1] - tol[p]) p= id[2 * i] + lc, i= 2 * i; else p= id[2 * i + 1] + rc, i= 2 * i + 1; } } T get(pos_t x, pos_t y) const { return val[xy2i(x, y) + id[2]]; } }; using namespace std; struct RSQ { using T= int; static T ti() { return 0; } static T op(T l, T r) { return l + r; } }; signed main() { cin.tie(0); ios::sync_with_stdio(0); int N; cin >> N; int A[N], L[N], R[N]; for (int i= 0; i < N; ++i) cin >> A[i]; for (int i= 0; i < N; ++i) cin >> L[i] >> R[i]; vector> v(N); for (int i= 0; i < N; i++) v[i]= {A[i], A[i] + R[i]}; SegmentTree_2D seg(v, 1); long long ans= 0; for (int i= 0; i < N; ++i) if (L[i] > 0) ans+= seg.fold(A[i] - L[i], A[i], A[i], 0x7fffffff); cout << ans << "\n"; return 0; }