#include //#define DEBUG 1 #define int long long #define for0(i,n) for (int i=0; i(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define all(a) a.begin(),a.end() #define sz(x) (int)(x).size() #define pmod(x,m) (((x)%(m)+m)%m) #ifdef int #define read(x) scanf("%lld",&x); #else #define read(x) scanf("%d",&x); #endif #ifdef DEBUG #define nl cout<<"\n"; #define pr(x) cout<<(x)<<" "; #define prl(x) cout<<#x " = "< interval_set; class IntervalTree { public: static bool comp_inc_l(interval a, interval b) { if (a.l == b.l) { //just to distinguish the intervals if (a.r == b.r) return a.i < b.i; return a.r < b.r; } return a.l < b.l; } static bool comp_inc_r(interval a, interval b) { if (a.r == b.r) { //just to distinguish the intervals if (a.l == b.l) return a.i < b.i; return a.l < b.l; } return a.r < b.r; } static bool comp_dec_r(interval a, interval b) { if (a.r == b.r) { //just to distinguish the intervals if (a.l == b.l) return a.i < b.i; return a.l < b.l; } return a.r > b.r; } static void print_interval_set(interval_set & S) { for (interval it : S) cout<<"("<r; S_mid.insert(*S_left_back); S_left.erase(S_left_back); for (; it!=S.end(); it++) { if (it->l <= x_center and x_center <= it->r) S_mid.insert(*it); else { assert(it->l > x_center); S_right.insert(*it); } } node * nd = new node(x_center, S_mid); nd->left_child = construct(S_left); nd->right_child = construct(S_right); return nd; } /*** Returns a vector of all intervals overlapping with x. If delete_results is true, all returned intervals will be deleted from the tree. ***/ vector get_overlap(int x, bool delete_results) { vector results; node * cur = root; while (cur != nullptr) { int tmp = results.size(); if (x <= cur->x_center) { //Go through intervals in this node in increasing order of l. //For all these intervals, r >= x_center >= x, so if l <= x //then they overlap for (auto it=cur->S_l.begin(); it!=cur->S_l.end(); it++) { if (it->l <= x) { //this interval overlaps results.push_back(*it); if (sz(results) >= 2) return results; } else //no more intervals here overlap break; } if (delete_results) { for (int i=tmp; iS_l.erase(results[i]); cur->S_r.erase(results[i]); } } cur = cur->left_child; } else { //Go through intervals in decreasing order of r. //Since l <= x_center < x, all these intervals overlap iff x <= r for (auto it=cur->S_r.begin(); it!=cur->S_r.end(); it++) { if (x <= it->r) { //this interval overlaps; results.push_back(*it); if (sz(results) >= 2) return results; } else //no more intervals here overlap break; } if (delete_results) { for (int i=tmp; iS_l.erase(results[i]); cur->S_r.erase(results[i]); } } cur = cur->right_child; } } return results; } }; ll pops[MAXN+5], cities[MAXN+5], clouds[MAXN+5], cloud_ranges[MAXN+5]; ll scores[MAXN+5]; int32_t main() { #ifdef DEBUG //freopen("B.txt","r",stdin); //freopen("","w",stdout); #endif int n,m; cin >> n; for0(i,n) { read(pops[i]); } for0(i,n) { read(cities[i]); } cin >> m; for0(i,m) { read(clouds[i]); } for0(i,m) { read(cloud_ranges[i]); } bool(*fn_pt)(interval,interval) = IntervalTree::comp_inc_r; interval_set S(fn_pt); for0(i,m) { S.insert(interval(clouds[i]-cloud_ranges[i], clouds[i]+cloud_ranges[i], i)); } IntervalTree interval_tree = IntervalTree(S); ms(scores,0); ll base_cnt = 0; for0(i,n) { vector overlaps = interval_tree.get_overlap(cities[i],false); if (sz(overlaps) == 1) { scores[overlaps[0].i] += pops[i]; } else if (sz(overlaps) == 0) { base_cnt += pops[i]; } } ll best = 0; for (int i=0; i