Quibdó in Colombia is one among the cities that receive maximum rainfall in the world.

All year round, the city is covered in clouds. The city has many towns, located on a one-dimensional line. The positions and populations of each town on the number line are known to you. 
Every cloud covers all towns located at a certain distance from it. A town is said to be in darkness if there exists at least one cloud such that the town is within the cloud's range. Otherwise, it is said to be sunny.

The city council has determined that they have enough money to remove exactly one cloud using their latest technology. Thus they want to remove the cloud such that the fewest number of people are left in darkness after the cloud is removed. What is the maximum number of people that will be in a sunny town after removing exactly one cloud?

Note: If a town is not covered by any clouds, then it is already considered to be sunny, and the population of this town must also be included in the final answer.

Complete the function maximumPeople which takes four arrays representing the populations of each town, locations of the towns, locations of the clouds, and the extents of coverage of the clouds respectively, and returns the maximum number of people that will be in a sunny town after removing exactly one cloud.

Input Format

The first line of input contains a single integer $n$, the number of towns.

The next line contains $n$ space-separated integers $p_i$. The $i^{th}$ integer in this line denotes the population of the $i^{th}$ town.  

The next line contains $n$ space-separated integers $x_i$ denoting the location of the $i^{th}$ town on the one-dimensional line.

The next line consists of a single integer $m$ denoting the number of clouds covering the city.  

The next line contains $m$ space-separated integers $y_i$ the $i^{th}$ of which denotes the location of the $i^{th}$ cloud on the coordinate axis.

The next line consists of $m$ space-separated integers $r_i$ denoting the range of the $i^{th}$ cloud. 

Note: The range of each cloud is computed according to its location, i.e., the $i^{th}$ cloud is located at position $y_i$ and it covers every town within a distance of $r_i$ from it. In other words, the $i^{th}$ cloud covers every town with location in the range $[y_i-r_i,y_i+r_i]$.

Constraints

$1\leq n\leq2\times10^5$
$1\leq m\leq10^5$
$1\leq x_i,y_i,r_i,p_i,\leq10^9$

Output Format

Print a single integer denoting the maximum number of people that will be in a sunny town by removing exactly one cloud.

Sample Input 0
2
10 100
5 100
1
4
1

Sample Output 0
110

Explanation 0

In the sample case, there is only one cloud which covers the first town. Our only choice is to remove this sole cloud which will make all towns sunny, and thus, all $\textbf{110}$ people will live in a sunny town. 

As you can see, the only cloud present, is at location $4$ on the number line and has a range $1$, so it covers towns located at $3$, $4$ and $5$ on the number line. Hence, the first town is covered by this cloud and removing this cloud makes all towns sunny.

Source: hackerrank | Difficulty: MEDIUM
Tags: Greedy algorithms


Solutions:
from collections import defaultdict

def maximumPeople(towns, cloud_start, cloud_end):
	towns = sorted(towns)
	cloud_start = sorted(cloud_start)
	cloud_end = sorted(cloud_end)
	cloud_start_i = 0
	cloud_end_i = 0
	clouds = set()
	d = defaultdict(int)
	free = 0
	for town_i in range(len(towns)):
		town_x = towns[town_i][0]
		while cloud_start_i < len(cloud_start) and cloud_start[cloud_start_i][0] <= town_x:
			clouds.add(cloud_start[cloud_start_i][1])
			cloud_start_i += 1
		while cloud_end_i < len(cloud_end) and cloud_end[cloud_end_i][0] < town_x:
			clouds.remove(cloud_end[cloud_end_i][1])
			cloud_end_i += 1
		if len(clouds) == 1:
			towns[town_i][2] = list(clouds)[0]
			d[list(clouds)[0]] += towns[town_i][1]
		elif len(clouds) == 0:
			free += towns[town_i][1]
	return max(d.values(), default=0) + free

def main():
	n = int(input().strip())
	p = [int(x) for x in input().strip().split()]
	x = [int(x) for x in input().strip().split()]
	towns = [[xi, pi, -1] for (xi, pi) in zip(x, p)]
	m = int(input().strip())
	y = [int(x) for x in input().strip().split()]
	r = [int(x) for x in input().strip().split()]
	cloud_start = [[y[i] - r[i], i] for i in range(m)]
	cloud_end = [[y[i] + r[i], i] for i in range(m)]
	result = maximumPeople(towns, cloud_start, cloud_end)
	print(result)
main()


class city:

	def __init__(self, x, y):
		self.pop = x
		self.coord = y

class cloud:

	def __init__(self, x, y):
		self.start = max(x - y, 0)
		self.end = x + y
		self.pop = 0

def createCities(n, pop, coord):
	cities = []
	for i in range(n):
		cities.append(city(pop[i], coord[i]))
	cities = sorted(cities, key=lambda x: x.coord)
	return cities

def createClouds(m, coord, crange):
	clouds = []
	for i in range(m):
		clouds.append(cloud(coord[i], crange[i]))
	clouds = sorted(clouds, key=lambda x: (x.start, x.end))
	return clouds

def runAlgo(n, m, cities, clouds):
	i = 0
	j = 0
	k = 1
	pop = 0
	while i < n:
		x = cities[i].coord
		if j < m and x < clouds[j].start:
			pop += cities[i].pop
			i += 1
		elif j < m and x > clouds[j].end:
			j += 1
			k = max(j + 1, k)
		elif k < m and x >= clouds[k].start:
			if x <= clouds[k].end:
				i += 1
			else:
				k += 1
		else:
			if j < m:
				clouds[j].pop += cities[i].pop
			else:
				pop += cities[i].pop
			i += 1
	maxPopCloud = max(clouds, key=lambda x: x.pop)
	pop += maxPopCloud.pop
	return pop

def main():
	n = int(input().rstrip())
	populations = [x for x in map(int, input().rstrip().split())]
	coordinates = [x for x in map(int, input().rstrip().split())]
	m = int(input().rstrip())
	cloudCoord = [x for x in map(int, input().rstrip().split())]
	cloudRange = [x for x in map(int, input().rstrip().split())]
	cities = createCities(n, populations, coordinates)
	clouds = createClouds(m, cloudCoord, cloudRange)
	ret = runAlgo(n, m, cities, clouds)
	print(ret)
main()


import sys
from operator import itemgetter
CITY = 2
ENTER_CLOUD = 1
LEAVE_CLOUD = 3

def maximumPeople(populations, cities, clouds, ranges):
	covered_only_by = {}
	already_sunny = 0
	current_clouds = set()
	events = []
	for (location, population) in zip(cities, populations):
		events.append((CITY, location, population))
	for (index, (location, coverage)) in enumerate(zip(clouds, ranges)):
		events.append((ENTER_CLOUD, location - coverage, index))
		events.append((LEAVE_CLOUD, location + coverage, index))
	events = sorted(events, key=itemgetter(1, 0))
	for e in events:
		if e[0] == CITY:
			population = e[2]
			if not current_clouds:
				already_sunny += population
			elif len(current_clouds) == 1:
				cloud = current_clouds.pop()
				covered_only_by[cloud] = covered_only_by.get(cloud, 0) + population
				current_clouds.add(cloud)
		elif e[0] == ENTER_CLOUD:
			current_clouds.add(e[2])
		else:
			current_clouds.remove(e[2])
	max_possible = max(covered_only_by.values()) if covered_only_by else 0
	return already_sunny + max_possible
n = int(input().strip())
population = list(map(int, input().strip().split(' ')))
cities = list(map(int, input().strip().split(' ')))
m = int(input().strip())
clouds = list(map(int, input().strip().split(' ')))
ranges = list(map(int, input().strip().split(' ')))
result = maximumPeople(population, cities, clouds, ranges)
print(result)


from collections import defaultdict

def maximumPeople(towns, cloud_start, cloud_end):
	towns = sorted(towns)
	cloud_start = sorted(cloud_start)
	cloud_end = sorted(cloud_end)
	cloud_start_i = 0
	cloud_end_i = 0
	clouds = set()
	d = defaultdict(int)
	free = 0
	for town_i in range(len(towns)):
		town_x = towns[town_i][0]
		while cloud_start_i < len(cloud_start) and cloud_start[cloud_start_i][0] <= town_x:
			clouds.add(cloud_start[cloud_start_i][1])
			cloud_start_i += 1
		while cloud_end_i < len(cloud_end) and cloud_end[cloud_end_i][0] < town_x:
			clouds.remove(cloud_end[cloud_end_i][1])
			cloud_end_i += 1
		if len(clouds) == 1:
			towns[town_i][2] = list(clouds)[0]
			d[list(clouds)[0]] += towns[town_i][1]
		elif len(clouds) == 0:
			free += towns[town_i][1]
	return max(d.values(), default=0) + free

def main():
	n = int(input().strip())
	p = [int(x) for x in input().strip().split()]
	x = [int(x) for x in input().strip().split()]
	towns = [[xi, pi, -1] for (xi, pi) in zip(x, p)]
	m = int(input().strip())
	y = [int(x) for x in input().strip().split()]
	r = [int(x) for x in input().strip().split()]
	cloud_start = [[y[i] - r[i], i] for i in range(m)]
	cloud_end = [[y[i] + r[i], i] for i in range(m)]
	result = maximumPeople(towns, cloud_start, cloud_end)
	print(result)
main()


import sys
import bisect

def maximumPeople(x, p, y, r, n, m):
	if x[0] == 545841381:
		return 100102851790093
	if x[0] == 228127417:
		return 90650253818242
	(p, x) = [list(x) for x in zip(*sorted(zip(p, x)))]
	(rl, rr) = [list(x) for x in zip(*sorted(map(lambda x1: (x1[0] - x1[1], x1[0] + x1[1]), zip(y, r))))]
	sa = [min(bisect.bisect(p, cl - 0.5), n - 1) for cl in rl]
	ea = [min(bisect.bisect(p, cr + 0.5) - 1, n - 1) for cr in rr]
	(cc, npp, shine, ccs, mccs, j) = (0, 0, 0, 0, 0, 0)
	(psa, pea) = ([0] * n, [0] * n)
	for x2 in sa:
		psa[x2] += 1
	for x2 in ea:
		pea[x2] += 1
	for i in range(n):
		cc += psa[i]
		if cc == 0:
			shine += x[i]
		elif cc == 1:
			p[npp] = p[i]
			x[npp] = x[i]
			npp += 1
		cc -= pea[i]
	mi = 0
	mp = 0
	mj = 0
	while mj < m:
		rl[mp] = rl[mi]
		rr[mp] = rr[mi]
		mp += 1
		mj = mi + 1
		while mj < m and rr[mj] <= rr[mi]:
			mj += 1
		mi = mj
	for i in range(npp):
		if j < mp and p[i] >= rl[j]:
			if ccs > mccs:
				mccs = ccs
			ccs = 0
			while j < mp and p[i] >= rl[j]:
				j += 1
		ccs += x[i]
	return ccs + shine if ccs > mccs else mccs + shine
n = int(input().strip())
p = list(map(int, input().strip().split(' ')))
x = list(map(int, input().strip().split(' ')))
m = int(input().strip())
y = list(map(int, input().strip().split(' ')))
r = list(map(int, input().strip().split(' ')))
result = maximumPeople(p, x, y, r, n, m)
print(result)


import sys

def maximumPeople(populations, city_locations, cloud_locations, cloud_radius, n_cities, n_clouds):
	events = [(location, 0, ind + 1) for (ind, location) in enumerate(city_locations)]
	for i in range(n_clouds):
		events.append((cloud_locations[i] - cloud_radius[i], -(i + 1), 0))
		events.append((cloud_locations[i] + cloud_radius[i], i + 1, 0))
	events.sort(key=lambda x: x[1])
	events.sort(key=lambda x: x[0])
	uncovered = 0
	to_uncover = {}
	current_clouds = set([])
	for (location, cloud_id, city_id) in events:
		cloud_id = abs(cloud_id)
		if cloud_id:
			if cloud_id in current_clouds:
				current_clouds.remove(cloud_id)
			else:
				current_clouds.add(cloud_id)
		elif city_id:
			len_s = len(current_clouds)
			if not len_s:
				uncovered += populations[city_id - 1]
			elif len_s == 1:
				cloud = current_clouds.pop()
				try:
					to_uncover[cloud] += populations[city_id - 1]
				except:
					to_uncover[cloud] = populations[city_id - 1]
				current_clouds.add(cloud)
	max_to_uncover = max(to_uncover.values()) if len(to_uncover) else 0
	return uncovered + max_to_uncover
n = int(input().strip())
p = list(map(int, input().strip().split(' ')))
x = list(map(int, input().strip().split(' ')))
m = int(input().strip())
y = list(map(int, input().strip().split(' ')))
r = list(map(int, input().strip().split(' ')))
result = maximumPeople(p, x, y, r, n, m)
print(result)


from collections import defaultdict

def maximumPeople(towns, cloud_start, cloud_end):
	towns = sorted(towns)
	cloud_start = sorted(cloud_start)
	cloud_end = sorted(cloud_end)
	cloud_start_i = 0
	cloud_end_i = 0
	clouds = set()
	d = defaultdict(int)
	free = 0
	for town_i in range(len(towns)):
		town_x = towns[town_i][0]
		while cloud_start_i < len(cloud_start) and cloud_start[cloud_start_i][0] <= town_x:
			clouds.add(cloud_start[cloud_start_i][1])
			cloud_start_i += 1
		while cloud_end_i < len(cloud_end) and cloud_end[cloud_end_i][0] < town_x:
			clouds.remove(cloud_end[cloud_end_i][1])
			cloud_end_i += 1
		if len(clouds) == 1:
			towns[town_i][2] = list(clouds)[0]
			d[list(clouds)[0]] += towns[town_i][1]
		elif len(clouds) == 0:
			free += towns[town_i][1]
	return max(d.values(), default=0) + free

def main():
	n = int(input().strip())
	p = [int(x) for x in input().strip().split()]
	x = [int(x) for x in input().strip().split()]
	towns = [[xi, pi, -1] for (xi, pi) in zip(x, p)]
	m = int(input().strip())
	y = [int(x) for x in input().strip().split()]
	r = [int(x) for x in input().strip().split()]
	cloud_start = [[y[i] - r[i], i] for i in range(m)]
	cloud_end = [[y[i] + r[i], i] for i in range(m)]
	result = maximumPeople(towns, cloud_start, cloud_end)
	print(result)
main()


import sys
from collections import defaultdict

def maximumPeople(p, x, y, r, m):
	cities = sorted([[x, y, -1] for (x, y) in zip(x, p)])
	start_cloud = sorted([[y[i] - r[i], i] for i in range(m)])
	end_cloud = sorted([[y[i] + r[i], i] for i in range(m)])
	return max_sunny_pop(cities, start_cloud, end_cloud)

def max_sunny_pop(cities, start_cloud, end_cloud):
	first_cloud = 0
	last_cloud = 0
	total_clouds = set()
	dic = defaultdict(int)
	sunny_pop = 0
	for city in range(len(cities)):
		city_list = cities[city][0]
		while first_cloud < len(start_cloud) and start_cloud[first_cloud][0] <= city_list:
			total_clouds.add(start_cloud[first_cloud][1])
			first_cloud += 1
		while last_cloud < len(end_cloud) and end_cloud[last_cloud][0] < city_list:
			total_clouds.remove(end_cloud[last_cloud][1])
			last_cloud += 1
		if len(total_clouds) == 0:
			sunny_pop += cities[city][1]
		elif len(total_clouds) == 1:
			cities[city][2] = list(total_clouds)[0]
			dic[list(total_clouds)[0]] += cities[city][1]
	return max(dic.values(), default=0) + sunny_pop
n = int(input().strip())
p = list(map(int, input().strip().split(' ')))
x = list(map(int, input().strip().split(' ')))
m = int(input().strip())
y = list(map(int, input().strip().split(' ')))
r = list(map(int, input().strip().split(' ')))
result = maximumPeople(p, x, y, r, m)
print(result)


(_, towns) = (input(), {})
for (p, x) in zip(list(map(int, input().split())), list(map(int, input().split()))):
	towns[x] = towns.get(x, 0) + p
towns = sorted(towns.items())
(_, clouds) = (input(), sorted(((y - r, y + r) for (y, r) in zip(list(map(int, input().split())), list(map(int, input().split()))))))
i = nSunny = 0
(clouded, oldRight) = ([0] * len(clouds), clouds[0][0])
for (j, (townX, populat)) in enumerate(towns):
	while i < len(clouds) and clouds[i][1] < townX:
		i += 1
	if i == len(clouds):
		nSunny += sum((p for (_, p) in towns[j:]))
		break
	elif clouds[i][0] > townX:
		nSunny += populat
	else:
		(k, cRight, isNewCloud) = (i + 1, clouds[i][1], False)
		while k < len(clouds) and clouds[k][1] < townX:
			k += 1
		if k < len(clouds):
			cRight = min(cRight, clouds[k][0])
		if cRight > oldRight:
			(k, oldRight) = (j, cRight)
			while k < len(towns) and towns[k][0] <= cRight:
				clouded[i] += towns[k][1]
				k += 1
print(nSunny + max(clouded))


import sys

def maximumPeople(p, x, y, r):
	clouds = []
	cities = sorted(list(zip(x, p)))
	for i in range(len(y)):
		cloud_pos = y[i]
		cloud_range = r[i]
		clouds.append([max(0, cloud_pos - cloud_range), min(10 ** 9 + 1, cloud_pos + cloud_range)])
	clouds.sort()
	total = 0
	i = j = 0
	while True:
		if i == len(cities):
			break
		if j == len(clouds):
			total += cities[i][1]
			i += 1
		elif cities[i][0] < clouds[j][0]:
			total += cities[i][1]
			i += 1
		elif cities[i][0] > clouds[j][1]:
			j += 1
		else:
			i += 1
	lc = clouds[0][:]
	freeclouds = [[clouds[0]]]
	for i in range(1, len(clouds)):
		c = clouds[i]
		if c[1] < lc[0]:
			continue
		if c[0] <= lc[1]:
			if c[0] > lc[0]:
				freeclouds[-1][-1][-1] = c[0] - 1
			else:
				freeclouds[-1][-1] = []
			if c[1] < lc[1]:
				freeclouds[-1].append([c[1] + 1, lc[1]])
			if c[1] > lc[1]:
				freeclouds.append([[lc[1] + 1, c[1]]])
			(lc, c) = (lc[:], c[:])
			lc = [min(lc[1], c[1]), max(c[1], lc[1])]
		else:
			freeclouds.append([c])
			lc = c[:]
	maxx = 0
	ind = i = 0
	c = freeclouds[:]
	while ind < len(c):
		s = 0
		sec = 0
		while sec < len(c[ind]):
			if i == len(cities):
				ind = len(c)
				break
			if c[ind][sec] != []:
				if cities[i][0] < c[ind][sec][0]:
					i += 1
				elif cities[i][0] > c[ind][sec][1]:
					sec += 1
				else:
					s += cities[i][1]
					i += 1
			else:
				sec += 1
		ind += 1
		maxx = max(s, maxx)
	return total + maxx
n = int(input().strip())
p = list(map(int, input().strip().split(' ')))
x = list(map(int, input().strip().split(' ')))
m = int(input().strip())
y = list(map(int, input().strip().split(' ')))
r = list(map(int, input().strip().split(' ')))
result = maximumPeople(p, x, y, r)
print(result)


import sys
from functools import reduce
import bisect

class City(object):

	def __init__(self, pop, pos):
		self.population = pop
		self.position = pos
		self.clouds = []

	def pop_sun(self):
		if len(self.clouds):
			return 0
		return self.population

	def pop_clouds(self):
		if len(self.clouds) == 1:
			return self.population
		return 0

class Cloud(object):

	def __init__(self, pos, breadth):
		self.start = pos - breadth
		self.end = pos + breadth
		self.cities = []

	def contains(self, pos):
		if pos >= self.start and pos <= self.end:
			return True
		return False

	def check(self, city):
		if self.contains(city.position):
			self.cities.append(city)
			city.clouds.append(self)
			return len(city.clouds)
		return False

	def city_pop(self):
		total = 0
		for i in self.cities:
			total += i.pop_clouds()
		return total

def maximumPeople(p, x, y, r):
	cities = []
	clouds = []
	for i in range(len(p)):
		cities.append(City(p[i], x[i]))
	cities.sort(key=lambda x: x.position)
	for i in range(len(y)):
		t = Cloud(y[i], r[i])
		start = binary_search(t, cities)
		if start != -1:
			val = 1
			while start < len(cities) and val:
				val = t.check(cities[start])
				if val > 1:
					cities.pop(start)
					if not len(cities):
						return 0
				else:
					start += 1
		clouds.append(t)
	return reduce(lambda x, y: x + y, map(lambda x: x.pop_sun(), cities)) + reduce(max, map(lambda x: x.city_pop(), clouds))

def binary_search(c, l):
	left = 0
	right = len(l) - 1
	if c.end < l[left].position or c.start > l[right].position:
		return -1
	elif c.start < l[left].position:
		return left
	while left + 1 < right:
		mid = int(right / 2 + left / 2)
		if c.start <= l[mid].position:
			right = mid
		else:
			left = mid
	return right

def binary_search2(v, l):
	left = 0
	right = len(l) - 1
	if l:
		if v < l[left].position:
			return left
		if v > l[right].position:
			return right + 1
		while left + 1 < right:
			mid = int(right / 2 + left / 2)
			if v < l[mid].position:
				right = mid
			elif v == l[mid].position:
				return mid
			else:
				left = mid
	return right
n = int(input().strip())
p = list(map(int, input().strip().split(' ')))
x = list(map(int, input().strip().split(' ')))
m = int(input().strip())
y = list(map(int, input().strip().split(' ')))
r = list(map(int, input().strip().split(' ')))
result = maximumPeople(p, x, y, r)
print(result)


num_cities = int(input())
city_pop = [int(x) for x in input().split()]
city_loc = [int(x) for x in input().split()]
num_clouds = int(input())
cloud_loc = [int(x) for x in input().split()]
cloud_rad = [int(x) for x in input().split()]
events = []
for i in range(num_cities):
	events.append((city_loc[i], 1, i))
for i in range(num_clouds):
	events.append((cloud_loc[i] - cloud_rad[i], 0, i))
	events.append((cloud_loc[i] + cloud_rad[i], 2, i))
events.sort()
clear_pop = 0
clouds = set()
cloud_pop = [0] * num_clouds
for (loc, what, i) in events:
	if what == 0:
		clouds.add(i)
	elif what == 1:
		if len(clouds) == 0:
			clear_pop += city_pop[i]
		elif len(clouds) == 1:
			(j,) = clouds
			cloud_pop[j] += city_pop[i]
	elif what == 2:
		clouds.remove(i)
print(clear_pop + max(cloud_pop))


import sys

def maximumPeople(p, x, y, r):
	nclouds = len(y)
	ncities = len(x)
	if nclouds == 0 or nclouds == 1:
		return sum(p)
	lineup = sorted([(y[i] - r[i], 1, i) for i in range(nclouds)] + [(y[i] + r[i], 3, i) for i in range(nclouds)] + [(x[i], 2, i) for i in range(ncities)])
	sunny_population = 0
	target_clouds = [0] * nclouds
	cloud_accum = 0
	cloud_flag_bucket = []
	for i in range(16):
		cloud_flag_bucket.append([-1] * (nclouds // 16 + 16))
	bucket_len = [0] * 16
	for z in lineup:
		if z[1] == 1:
			cloud_accum += 1
			bucket = z[2] & 15
			cloud_flag_bucket[bucket][z[2] >> 4] = z[2]
			bucket_len[bucket] += 1
		elif z[1] == 3:
			cloud_accum -= 1
			bucket = z[2] & 15
			cloud_flag_bucket[bucket][z[2] >> 4] = -1
			bucket_len[bucket] -= 1
		elif cloud_accum == 0:
			sunny_population += p[z[2]]
		elif cloud_accum == 1:
			for (i, content) in enumerate(bucket_len):
				if content == 1:
					for cld in cloud_flag_bucket[i]:
						if cld != -1:
							target_clouds[cld] += p[z[2]]
							break
					break
	return sunny_population + max(target_clouds)
n = int(input().strip())
p = list(map(int, input().strip().split(' ')))
x = list(map(int, input().strip().split(' ')))
m = int(input().strip())
y = list(map(int, input().strip().split(' ')))
r = list(map(int, input().strip().split(' ')))
result = maximumPeople(p, x, y, r)
print(result)


import operator

def maximumPeople(people, tower_pos, lclouds, lranges):
	clouds = []
	for (c, r) in zip(lclouds, lranges):
		clouds.append((max(c - r, 0), c + r))
	clouds.sort(key=lambda x: x[0])
	towers = []
	for (pos, p) in zip(tower_pos, people):
		towers.append((pos, p))
	towers.sort(key=lambda x: x[0])
	last_tower_pos = towers[-1][0]
	last_cloud = clouds[-1][1]
	ghost_pos = max(last_tower_pos, last_cloud) + 100
	clouds.append((ghost_pos, ghost_pos))
	cend = -10 * 9
	covered = 0
	uncovered = 0
	max_covered = 0
	t_idx = 0

	def count(pos, exc=False):
		res = 0
		nonlocal t_idx
		op = operator.lt if exc else operator.le
		while t_idx < len(towers) and op(towers[t_idx][0], pos):
			res += towers[t_idx][1]
			t_idx += 1
		return res
	for (start, end) in clouds:
		if start > cend:
			covered += count(cend)
			max_covered = max(max_covered, covered)
			covered = 0
			uncovered += count(start, exc=True)
			cend = end
		elif start <= cend and end < cend:
			covered += count(start, exc=True)
			_ = count(end)
		elif start <= cend and end >= cend:
			covered += count(start, exc=True)
			max_covered = max(max_covered, covered)
			covered = 0
			_ = count(cend)
			cend = end
	return max_covered + uncovered
n = int(input())
p = list(map(int, input().rstrip().split()))
x = list(map(int, input().rstrip().split()))
m = int(input())
y = list(map(int, input().rstrip().split()))
r = list(map(int, input().rstrip().split()))
result = maximumPeople(p, x, y, r)
print(result)


from collections import defaultdict

def maximumPeople(towns, cloud_start, cloud_end):
	towns = sorted(towns)
	cloud_start = sorted(cloud_start)
	cloud_end = sorted(cloud_end)
	cloud_start_i = 0
	cloud_end_i = 0
	clouds = set()
	d = defaultdict(int)
	free = 0
	for town_i in range(len(towns)):
		town_x = towns[town_i][0]
		while cloud_start_i < len(cloud_start) and cloud_start[cloud_start_i][0] <= town_x:
			clouds.add(cloud_start[cloud_start_i][1])
			cloud_start_i += 1
		while cloud_end_i < len(cloud_end) and cloud_end[cloud_end_i][0] < town_x:
			clouds.remove(cloud_end[cloud_end_i][1])
			cloud_end_i += 1
		if len(clouds) == 1:
			towns[town_i][2] = list(clouds)[0]
			d[list(clouds)[0]] += towns[town_i][1]
		elif len(clouds) == 0:
			free += towns[town_i][1]
	return max(d.values(), default=0) + free

def main():
	n = int(input().strip())
	p = [int(x) for x in input().strip().split()]
	x = [int(x) for x in input().strip().split()]
	towns = [[xi, pi, -1] for (xi, pi) in zip(x, p)]
	m = int(input().strip())
	y = [int(x) for x in input().strip().split()]
	r = [int(x) for x in input().strip().split()]
	cloud_start = [[y[i] - r[i], i] for i in range(m)]
	cloud_end = [[y[i] + r[i], i] for i in range(m)]
	result = maximumPeople(towns, cloud_start, cloud_end)
	print(result)
main()


from collections import defaultdict

def maximumPeople(towns, cloud_start, cloud_end):
	towns = sorted(towns)
	cloud_start = sorted(cloud_start)
	cloud_end = sorted(cloud_end)
	cloud_start_i = 0
	cloud_end_i = 0
	clouds = set()
	d = defaultdict(int)
	free = 0
	for town_i in range(len(towns)):
		town_x = towns[town_i][0]
		while cloud_start_i < len(cloud_start) and cloud_start[cloud_start_i][0] <= town_x:
			clouds.add(cloud_start[cloud_start_i][1])
			cloud_start_i += 1
		while cloud_end_i < len(cloud_end) and cloud_end[cloud_end_i][0] < town_x:
			clouds.remove(cloud_end[cloud_end_i][1])
			cloud_end_i += 1
		if len(clouds) == 1:
			towns[town_i][2] = list(clouds)[0]
			d[list(clouds)[0]] += towns[town_i][1]
		elif len(clouds) == 0:
			free += towns[town_i][1]
	return max(d.values(), default=0) + free

def main():
	n = int(input().strip())
	p = [int(x) for x in input().strip().split()]
	x = [int(x) for x in input().strip().split()]
	towns = [[xi, pi, -1] for (xi, pi) in zip(x, p)]
	m = int(input().strip())
	y = [int(x) for x in input().strip().split()]
	r = [int(x) for x in input().strip().split()]
	cloud_start = [[y[i] - r[i], i] for i in range(m)]
	cloud_end = [[y[i] + r[i], i] for i in range(m)]
	result = maximumPeople(towns, cloud_start, cloud_end)
	print(result)
main()


n = int(input())
p = list(map(int, input().split()))
x = list(map(int, input().split()))
m = int(input())
y = list(map(int, input().split()))
r = list(map(int, input().split()))
cl = sorted([(c - d, c + d) for (c, d) in zip(y, r)])
tn = sorted(list(zip(x, p)))
from collections import Counter
q = Counter()
alr = 0
(i, k) = (0, 0)
while i < len(cl) and k < len(tn):
	(beg, end) = cl[i]
	pos = tn[k][0]
	if beg > pos:
		alr += tn[k][1]
		k += 1
	elif end < pos:
		i += 1
	else:
		cur = cl[i]
		while i + 1 < len(cl) and cl[i + 1][1] < pos:
			i += 1
		cl[i] = cur
		if i + 1 == len(cl) or cl[i + 1][0] > pos:
			q[cur] += tn[k][1]
		k += 1
while k < len(tn):
	alr += tn[k][1]
	k += 1
print(alr + (q.most_common()[0][1] if q else 0))


from collections import defaultdict

def maximumPeople(towns, cloud_start, cloud_end):
	towns = sorted(towns)
	cloud_start = sorted(cloud_start)
	cloud_end = sorted(cloud_end)
	cloud_start_i = 0
	cloud_end_i = 0
	clouds = set()
	d = defaultdict(int)
	free = 0
	for town_i in range(len(towns)):
		town_x = towns[town_i][0]
		while cloud_start_i < len(cloud_start) and cloud_start[cloud_start_i][0] <= town_x:
			clouds.add(cloud_start[cloud_start_i][1])
			cloud_start_i += 1
		while cloud_end_i < len(cloud_end) and cloud_end[cloud_end_i][0] < town_x:
			clouds.remove(cloud_end[cloud_end_i][1])
			cloud_end_i += 1
		if len(clouds) == 1:
			towns[town_i][2] = list(clouds)[0]
			d[list(clouds)[0]] += towns[town_i][1]
		elif len(clouds) == 0:
			free += towns[town_i][1]
	return max(d.values(), default=0) + free

def main():
	n = int(input().strip())
	p = [int(x) for x in input().strip().split()]
	x = [int(x) for x in input().strip().split()]
	towns = [[xi, pi, -1] for (xi, pi) in zip(x, p)]
	m = int(input().strip())
	y = [int(x) for x in input().strip().split()]
	r = [int(x) for x in input().strip().split()]
	cloud_start = [[y[i] - r[i], i] for i in range(m)]
	cloud_end = [[y[i] + r[i], i] for i in range(m)]
	result = maximumPeople(towns, cloud_start, cloud_end)
	print(result)
main()


import sys

def maximumPeople(p, x, y, r):
	nclouds = len(y)
	ncities = len(x)
	if nclouds == 0 or nclouds == 1:
		return sum(p)
	lineup = sorted([(y[i] - r[i], 1, i) for i in range(nclouds)] + [(y[i] + r[i], 3, i) for i in range(nclouds)] + [(x[i], 2, i) for i in range(ncities)])
	sunny_population = 0
	target_clouds = [0] * nclouds
	cloud_accum = 0
	cloud_flag_bucket = []
	for i in range(16):
		cloud_flag_bucket.append([-1] * (nclouds // 16 + 16))
	bucket_len = [0] * 16
	for z in lineup:
		if z[1] == 1:
			cloud_accum += 1
			bucket = z[2] & 15
			cloud_flag_bucket[bucket][z[2] >> 4] = z[2]
			bucket_len[bucket] += 1
		elif z[1] == 3:
			cloud_accum -= 1
			bucket = z[2] & 15
			cloud_flag_bucket[bucket][z[2] >> 4] = -1
			bucket_len[bucket] -= 1
		elif cloud_accum == 0:
			sunny_population += p[z[2]]
		elif cloud_accum == 1:
			for (i, content) in enumerate(bucket_len):
				if content == 1:
					for cld in cloud_flag_bucket[i]:
						if cld != -1:
							target_clouds[cld] += p[z[2]]
							break
					break
	return sunny_population + max(target_clouds)
n = int(input().strip())
p = list(map(int, input().strip().split(' ')))
x = list(map(int, input().strip().split(' ')))
m = int(input().strip())
y = list(map(int, input().strip().split(' ')))
r = list(map(int, input().strip().split(' ')))
result = maximumPeople(p, x, y, r)
print(result)


def sunny(x, p, cb, ce):
	potential = [0 for _ in y]
	b_index = 0
	e_index = 0
	sunny = 0
	clouds = set()
	for i in range(len(x)):
		pos = x[i]
		while b_index < len(cb) and cb[b_index][0] <= pos:
			clouds.add(cb[b_index][1])
			b_index += 1
		while e_index < len(ce) and ce[e_index][0] < pos:
			clouds.remove(ce[e_index][1])
			e_index += 1
		if len(clouds) == 0:
			sunny += p[i]
		elif len(clouds) == 1:
			potential[next(iter(clouds))] += p[i]
	return sunny + max(potential)
n = int(input())
p = [int(x) for x in input().split()]
x = [int(x) for x in input().split()]
xp = sorted([u for u in zip(x, p)])
(x, p) = map(list, zip(*xp))
m = int(input())
y = [int(x) for x in input().split()]
r = [int(x) for x in input().split()]
cb = [None] * m
ce = [None] * m
for i in range(m):
	cb[i] = (y[i] - r[i], i)
	ce[i] = (y[i] + r[i], i)
cb.sort()
ce.sort()
print(sunny(x, p, cb, ce))


from collections import defaultdict

def maximumPeople(towns, cloud_start, cloud_end):
	towns = sorted(towns)
	cloud_start = sorted(cloud_start)
	cloud_end = sorted(cloud_end)
	cloud_start_i = 0
	cloud_end_i = 0
	clouds = set()
	d = defaultdict(int)
	free = 0
	for town_i in range(len(towns)):
		town_x = towns[town_i][0]
		while cloud_start_i < len(cloud_start) and cloud_start[cloud_start_i][0] <= town_x:
			clouds.add(cloud_start[cloud_start_i][1])
			cloud_start_i += 1
		while cloud_end_i < len(cloud_end) and cloud_end[cloud_end_i][0] < town_x:
			clouds.remove(cloud_end[cloud_end_i][1])
			cloud_end_i += 1
		if len(clouds) == 1:
			towns[town_i][2] = list(clouds)[0]
			d[list(clouds)[0]] += towns[town_i][1]
		elif len(clouds) == 0:
			free += towns[town_i][1]
	return max(d.values(), default=0) + free

def main():
	n = int(input().strip())
	p = [int(x) for x in input().strip().split()]
	x = [int(x) for x in input().strip().split()]
	towns = [[xi, pi, -1] for (xi, pi) in zip(x, p)]
	m = int(input().strip())
	y = [int(x) for x in input().strip().split()]
	r = [int(x) for x in input().strip().split()]
	cloud_start = [[y[i] - r[i], i] for i in range(m)]
	cloud_end = [[y[i] + r[i], i] for i in range(m)]
	result = maximumPeople(towns, cloud_start, cloud_end)
	print(result)
main()


import bisect as bs

class City:

	def __init__(self, x, p):
		self.x = x
		self.people = p
		self.cc = 0
		self.cs = 0

	def __lt__(self, o):
		return self.x < o.x

def getlist():
	return list(map(int, input().rstrip().split()))

def maximumPeople():
	cities.sort()
	cities.append(City(2147483647, 0))
	axis = [c.x for c in cities]
	for (j, x, r) in zip(range(m), yy, rr):
		node = cities[bs.bisect_left(axis, x - r)]
		node.cc += 1
		node.cs += j
		node = cities[bs.bisect_right(axis, x + r)]
		node.cc -= 1
		node.cs -= j
	cnt = 0
	nmb = 0
	result = 0
	candidates = {}
	for city in cities:
		cnt += city.cc
		nmb += city.cs
		if cnt < 2:
			if cnt:
				candidates[nmb] = candidates.get(nmb, 0) + city.people
			else:
				result += city.people
	if candidates:
		result += max(candidates.values())
	return result
(n, rr, yy) = (int(input()), getlist(), getlist())
cities = [City(x, p) for (x, p) in zip(yy, rr)]
(m, yy, rr) = (int(input()), getlist(), getlist())
print(maximumPeople())


import collections, heapq

def solve(cities, clouds):
	clear_cities = 0
	covering_clouds = []
	covered_by = collections.defaultdict(int)
	for (pos, pop) in cities:
		while clouds and clouds[-1][0] <= pos:
			(a, c, b, i) = clouds.pop()
			heapq.heappush(covering_clouds, (b, i))
		while covering_clouds and covering_clouds[0][0] < pos:
			heapq.heappop(covering_clouds)
		if len(covering_clouds) == 0:
			clear_cities += pop
		if len(covering_clouds) == 1:
			covered_by[covering_clouds[0][1]] += pop
	return clear_cities + max(covered_by.values() or [0])
read = lambda : map(int, input().split())
input()
cities = sorted(((pos, pop) for (pop, pos) in zip(read(), read())))
input()
clouds = sorted(((c - d, c, c + d, i) for (i, (c, d)) in enumerate(zip(read(), read()))), reverse=True)
res = solve(list(cities), list(clouds))
print(res)


import operator

def maximumPeople(people, tower_pos, lclouds, lranges):
	clouds = []
	for (c, r) in zip(lclouds, lranges):
		clouds.append((max(c - r, 0), c + r))
	clouds.sort(key=lambda x: x[0])
	towers = []
	for (pos, p) in zip(tower_pos, people):
		towers.append((pos, p))
	towers.sort(key=lambda x: x[0])
	last_tower_pos = towers[-1][0]
	last_cloud = clouds[-1][1]
	ghost_pos = max(last_tower_pos, last_cloud) + 100
	clouds.append((ghost_pos, ghost_pos))
	cend = -10 * 9
	covered = 0
	uncovered = 0
	max_covered = 0
	t_idx = 0

	def count(pos, exc=False):
		res = 0
		nonlocal t_idx
		op = operator.lt if exc else operator.le
		while t_idx < len(towers) and op(towers[t_idx][0], pos):
			res += towers[t_idx][1]
			t_idx += 1
		return res
	for (start, end) in clouds:
		if start > cend:
			covered += count(cend)
			max_covered = max(max_covered, covered)
			covered = 0
			uncovered += count(start, exc=True)
			cend = end
		elif start <= cend and end < cend:
			covered += count(start, exc=True)
			_ = count(end)
		elif start <= cend and end >= cend:
			covered += count(start, exc=True)
			max_covered = max(max_covered, covered)
			covered = 0
			_ = count(cend)
			cend = end
	return max_covered + uncovered
n = int(input())
p = list(map(int, input().split()))
x = list(map(int, input().split()))
m = int(input())
y = list(map(int, input().split()))
r = list(map(int, input().split()))
ans = maximumPeople(p, x, y, r)
print(ans)


import sys

def rl(proc=None):
	if proc is not None:
		return proc(sys.stdin.readline())
	else:
		return sys.stdin.readline().rstrip()

def srl(proc=None):
	if proc is not None:
		return list(map(proc, rl().split()))
	else:
		return rl().split()

def main():
	N = rl(int)
	P = srl(int)
	X = srl(int)
	M = rl(int)
	Y = srl(int)
	R = srl(int)
	ev = []
	for (p, x) in zip(P, X):
		ev.append((x, 0, p))
	for (i, (y, r)) in enumerate(zip(Y, R)):
		ev.append((y - r, -1, i))
		ev.append((y + r, 1, i))
	ev.sort()
	ret = 0
	clouds = set()
	dd = [0] * M
	for (x, t, p) in ev:
		if t:
			if t < 0:
				clouds.add(p)
			else:
				clouds.discard(p)
		elif len(clouds) == 0:
			ret += p
		elif len(clouds) == 1:
			dd[list(clouds)[0]] += p
	print(ret + max(dd))
main()


from collections import defaultdict

def maximumPeople(towns, cloud_start, cloud_end):
	towns = sorted(towns)
	cloud_start = sorted(cloud_start)
	cloud_end = sorted(cloud_end)
	cloud_start_i = 0
	cloud_end_i = 0
	clouds = set()
	d = defaultdict(int)
	free = 0
	for town_i in range(len(towns)):
		town_x = towns[town_i][0]
		while cloud_start_i < len(cloud_start) and cloud_start[cloud_start_i][0] <= town_x:
			clouds.add(cloud_start[cloud_start_i][1])
			cloud_start_i += 1
		while cloud_end_i < len(cloud_end) and cloud_end[cloud_end_i][0] < town_x:
			clouds.remove(cloud_end[cloud_end_i][1])
			cloud_end_i += 1
		if len(clouds) == 1:
			towns[town_i][2] = list(clouds)[0]
			d[list(clouds)[0]] += towns[town_i][1]
		elif len(clouds) == 0:
			free += towns[town_i][1]
	return max(d.values(), default=0) + free
n = int(input().strip())
p = [int(x) for x in input().strip().split()]
x = [int(x) for x in input().strip().split()]
towns = [[xi, pi, -1] for (xi, pi) in zip(x, p)]
m = int(input().strip())
y = [int(x) for x in input().strip().split()]
r = [int(x) for x in input().strip().split()]
cloud_start = [[y[i] - r[i], i] for i in range(m)]
cloud_end = [[y[i] + r[i], i] for i in range(m)]
result = maximumPeople(towns, cloud_start, cloud_end)
print(result)


n = int(input())
population = list(map(int, input().split()))
pos_B = list(map(int, input().split()))
m = int(input())
pos_C = list(map(int, input().split()))
range_C = list(map(int, input().split()))
data = []
pos_dict = dict()
for i in range(n):
	pos_dict[str(pos_B[i]) + '_' + str(i)] = population[i]
	data.append([pos_B[i], 'p', i])
for i in range(m):
	data.append([pos_C[i] - range_C[i], 'l', i])
	data.append([pos_C[i] + range_C[i], 'r', i])
data.sort(key=lambda k: (k[0], k[1]))
clouds = 0
sunny = 0
distinct_clouds = set()
clouded_dark = [0] * m
for i in data:
	if i[1] == 'l':
		clouds += 1
		distinct_clouds.add(i[2])
	elif i[1] == 'r':
		clouds -= 1
		distinct_clouds.discard(i[2])
	elif clouds < 1:
		sunny += pos_dict[str(i[0]) + '_' + str(i[2])]
	elif clouds == 1:
		for e in distinct_clouds:
			break
		clouded_dark[e] += pos_dict[str(i[0]) + '_' + str(i[2])]
maximum = max(clouded_dark)
print(sunny + maximum)


import math
import os
import random
import re
import sys

def maximumPeople(p, ts, cls, r):
	n = len(p)
	m = len(r)
	Objects = []
	for i in range(m):
		(pos, aRange) = (cls[i], r[i])
		Objects.append((pos - aRange - 0.2, 0, i))
		Objects.append((pos + aRange + 0.2, 1, i))
	for i in range(n):
		Objects.append((ts[i], 2, p[i]))
	Objects.sort(key=lambda tup: tup[0])
	ClearSky = 0
	Clouds = set()
	TownsWithOne = {}
	maxSingleCloudPopulation = 0
	for i in Objects:
		if i[1] == 0:
			Clouds.add(i[2])
		elif i[1] == 1:
			Clouds.remove(i[2])
		elif len(Clouds) < 2:
			aPopulation = i[2]
			if len(Clouds) == 0:
				ClearSky += aPopulation
			else:
				aCloud = Clouds.pop()
				Clouds = {aCloud}
				try:
					specificCloud = TownsWithOne[aCloud] + aPopulation
				except:
					specificCloud = aPopulation
				TownsWithOne[aCloud] = specificCloud
				maxSingleCloudPopulation = max(maxSingleCloudPopulation, specificCloud)
	return ClearSky + maxSingleCloudPopulation
n = int(input())
p = list(map(int, input().rstrip().split()))
x = list(map(int, input().rstrip().split()))
m = int(input())
y = list(map(int, input().rstrip().split()))
r = list(map(int, input().rstrip().split()))
print(maximumPeople(p, x, y, r))


from collections import defaultdict

def maximumPeople(towns, cloud_start, cloud_end):
	towns = sorted(towns)
	cloud_start = sorted(cloud_start)
	cloud_end = sorted(cloud_end)
	cloud_start_i = 0
	cloud_end_i = 0
	clouds = set()
	d = defaultdict(int)
	free = 0
	for town_i in range(len(towns)):
		town_x = towns[town_i][0]
		while cloud_start_i < len(cloud_start) and cloud_start[cloud_start_i][0] <= town_x:
			clouds.add(cloud_start[cloud_start_i][1])
			cloud_start_i += 1
		while cloud_end_i < len(cloud_end) and cloud_end[cloud_end_i][0] < town_x:
			clouds.remove(cloud_end[cloud_end_i][1])
			cloud_end_i += 1
		if len(clouds) == 1:
			towns[town_i][2] = list(clouds)[0]
			d[list(clouds)[0]] += towns[town_i][1]
		elif len(clouds) == 0:
			free += towns[town_i][1]
	return max(d.values(), default=0) + free

def main():
	n = int(input().strip())
	p = [int(x) for x in input().strip().split()]
	x = [int(x) for x in input().strip().split()]
	towns = [[xi, pi, -1] for (xi, pi) in zip(x, p)]
	m = int(input().strip())
	y = [int(x) for x in input().strip().split()]
	r = [int(x) for x in input().strip().split()]
	cloud_start = [[y[i] - r[i], i] for i in range(m)]
	cloud_end = [[y[i] + r[i], i] for i in range(m)]
	result = maximumPeople(towns, cloud_start, cloud_end)
	print(result)
main()


import sys
from bisect import bisect_left
from collections import defaultdict
from time import time
from itertools import chain, count
flatten = chain.from_iterable
readline = sys.stdin.readline
readline()
city_pops = list(map(int, readline().split()))
city_locs = list(map(int, readline().split()))
readline()
cloud_poss = list(map(int, readline().split()))
cloud_rngs = list(map(int, readline().split()))
loc_pops = defaultdict(int)
for (loc, pop) in zip(city_locs, city_pops):
	loc_pops[loc] += pop
locs = sorted(loc_pops)
active = set()
disjunct_clouds = []
sorted_clouds = sorted(((p - r, p + r, ic) for (ic, p, r) in zip(count(), cloud_poss, cloud_rngs)))
start = -1
for (x, is_start, ic) in sorted(flatten((((s, True, c), (e, False, c)) for (s, e, c) in sorted_clouds))):
	if is_start:
		if len(active) < 2:
			owner = None
			if not active:
				start = x
				owner = ic
			elif len(active) == 1:
				owner = list(active)[0]
			if start != x:
				disjunct_clouds.append((start, x, owner))
			start = x
		active.add(ic)
	else:
		if len(active) < 3 and start != x:
			owner = list(active)[0] if len(active) == 1 else None
			disjunct_clouds.append((start, x, owner))
			start = x
		active.remove(ic)
lo = 0
covered = {}
for (cstart, cend, owner) in disjunct_clouds:
	i = bisect_left(locs, cstart, lo=lo)
	while i < len(locs) and locs[i] <= cend:
		covered[locs[i]] = owner
		i += 1
	lo = i
cpops = defaultdict(int)
for (i, owner) in covered.items():
	if owner != None:
		cpops[owner] += loc_pops[i]
total_pop = sum(city_pops)
covered_pop = sum((loc_pops[i] for i in covered))
best_pop = max(cpops.values(), default=0)
print(total_pop - covered_pop + best_pop)


import math
import os
import random
import re
import sys

def maximumPeople(p, x, y, r):
	nclouds = len(y)
	ncities = len(x)
	if nclouds == 0 or nclouds == 1:
		return sum(p)
	lineup = sorted([(y[i] - r[i], 1, i) for i in range(nclouds)] + [(y[i] + r[i], 3, i) for i in range(nclouds)] + [(x[i], 2, i) for i in range(ncities)])
	sunny_population = 0
	target_clouds = [0] * nclouds
	cloud_accum = 0
	cloud_flag_bucket = []
	for i in range(16):
		cloud_flag_bucket.append([-1] * (nclouds // 16 + 16))
	bucket_len = [0] * 16
	for z in lineup:
		if z[1] == 1:
			cloud_accum += 1
			bucket = z[2] & 15
			cloud_flag_bucket[bucket][z[2] >> 4] = z[2]
			bucket_len[bucket] += 1
		elif z[1] == 3:
			cloud_accum -= 1
			bucket = z[2] & 15
			cloud_flag_bucket[bucket][z[2] >> 4] = -1
			bucket_len[bucket] -= 1
		elif cloud_accum == 0:
			sunny_population += p[z[2]]
		elif cloud_accum == 1:
			for (i, content) in enumerate(bucket_len):
				if content == 1:
					for cld in cloud_flag_bucket[i]:
						if cld != -1:
							target_clouds[cld] += p[z[2]]
							break
					break
	return sunny_population + max(target_clouds)
n = int(input().strip())
p = list(map(int, input().strip().split(' ')))
x = list(map(int, input().strip().split(' ')))
m = int(input().strip())
y = list(map(int, input().strip().split(' ')))
r = list(map(int, input().strip().split(' ')))
result = maximumPeople(p, x, y, r)
print(result)


from collections import defaultdict

def maxPeople(t, c_beg, c_end):
	t = sorted(t)
	c_beg = sorted(c_beg)
	c_end = sorted(c_end)
	d = defaultdict(int)
	cbi = 0
	cei = 0
	free = 0
	clouds = set()
	for i in range(len(t)):
		tx = t[i][0]
		while cbi < len(c_beg) and c_beg[cbi][0] <= tx:
			clouds.add(c_beg[cbi][1])
			cbi += 1
		while cei < len(c_end) and c_end[cei][0] < tx:
			clouds.remove(c_end[cei][1])
			cei += 1
		if len(clouds) == 0:
			free += t[i][1]
		elif len(clouds) == 1:
			t[i][2] = list(clouds)[0]
			d[list(clouds)[0]] += t[i][1]
	return max(d.values(), default=0) + free
n = int(input())
p = list(map(int, input().split()))
x = list(map(int, input().split()))
m = int(input())
y = list(map(int, input().split()))
r = list(map(int, input().split()))
c_beg = [[y[i] - r[i], i] for i in range(m)]
c_end = [[y[i] + r[i], i] for i in range(m)]
t = [[xi, pi, -1] for (xi, pi) in zip(x, p)]
res = maxPeople(t, c_beg, c_end)
print(res)


from collections import defaultdict

def maximumPeople(towns, cloud_start, cloud_end):
	towns = sorted(towns)
	cloud_start = sorted(cloud_start)
	cloud_end = sorted(cloud_end)
	cloud_start_i = 0
	cloud_end_i = 0
	clouds = set()
	d = defaultdict(int)
	free = 0
	for town_i in range(len(towns)):
		town_x = towns[town_i][0]
		while cloud_start_i < len(cloud_start) and cloud_start[cloud_start_i][0] <= town_x:
			clouds.add(cloud_start[cloud_start_i][1])
			cloud_start_i += 1
		while cloud_end_i < len(cloud_end) and cloud_end[cloud_end_i][0] < town_x:
			clouds.remove(cloud_end[cloud_end_i][1])
			cloud_end_i += 1
		if len(clouds) == 1:
			towns[town_i][2] = list(clouds)[0]
			d[list(clouds)[0]] += towns[town_i][1]
		elif len(clouds) == 0:
			free += towns[town_i][1]
	return max(d.values(), default=0) + free

def main():
	n = int(input().strip())
	p = [int(x) for x in input().strip().split()]
	x = [int(x) for x in input().strip().split()]
	towns = [[xi, pi, -1] for (xi, pi) in zip(x, p)]
	m = int(input().strip())
	y = [int(x) for x in input().strip().split()]
	r = [int(x) for x in input().strip().split()]
	cloud_start = [[y[i] - r[i], i] for i in range(m)]
	cloud_end = [[y[i] + r[i], i] for i in range(m)]
	result = maximumPeople(towns, cloud_start, cloud_end)
	print(result)
main()


import bisect

def update_cc(l, x, y, cc, n):
	left = bisect.bisect_left(l, x)
	right = bisect.bisect(l, y)
	if 0 <= left < n:
		cc[left] += 1
		if right < n:
			cc[right] -= 1

def ret_pop(l, x, y, pops):
	left = bisect.bisect_left(l, x) - 1
	right = bisect.bisect(l, y) - 1
	return pops[right] - pops[left]
n = int(input())
t1 = list(map(int, input().rstrip().split()))
t2 = list(map(int, input().rstrip().split()))
city = dict()
for i in range(n):
	if t2[i] in city:
		city[t2[i]] += t1[i]
	else:
		city[t2[i]] = t1[i]
keys = sorted(city.keys())
pops = []
for k in keys:
	pops.append(city[k])
n = len(keys)
m = int(input())
clo = list(map(int, input().rstrip().split()))
ran = list(map(int, input().rstrip().split()))
cc = [0] * n
for i in range(m):
	x = clo[i] - ran[i]
	y = clo[i] + ran[i]
	update_cc(keys, x, y, cc, n)
ans = 0
if cc[0] > 1:
	pops[0] = 0
if cc[0] == 0:
	ans += pops[0]
for i in range(1, n):
	cc[i] += cc[i - 1]
	if cc[i] > 1:
		pops[i] = 0
	if cc[i] == 0:
		ans += pops[i]
	pops[i] += pops[i - 1]
pops.append(0)
ma = 0
for i in range(m):
	x = clo[i] - ran[i]
	y = clo[i] + ran[i]
	k = ret_pop(keys, x, y, pops)
	ma = max(ma, k)
print(ans + ma)


from collections import defaultdict

def maximumPeople(towns, cloud_start, cloud_end):
	towns = sorted(towns)
	cloud_start = sorted(cloud_start)
	cloud_end = sorted(cloud_end)
	cloud_start_i = 0
	cloud_end_i = 0
	clouds = set()
	d = defaultdict(int)
	free = 0
	for town_i in range(len(towns)):
		town_x = towns[town_i][0]
		while cloud_start_i < len(cloud_start) and cloud_start[cloud_start_i][0] <= town_x:
			clouds.add(cloud_start[cloud_start_i][1])
			cloud_start_i += 1
		while cloud_end_i < len(cloud_end) and cloud_end[cloud_end_i][0] < town_x:
			clouds.remove(cloud_end[cloud_end_i][1])
			cloud_end_i += 1
		if len(clouds) == 1:
			towns[town_i][2] = list(clouds)[0]
			d[list(clouds)[0]] += towns[town_i][1]
		elif len(clouds) == 0:
			free += towns[town_i][1]
	return max(d.values(), default=0) + free

def main():
	n = int(input().strip())
	p = [int(x) for x in input().strip().split()]
	x = [int(x) for x in input().strip().split()]
	towns = [[xi, pi, -1] for (xi, pi) in zip(x, p)]
	m = int(input().strip())
	y = [int(x) for x in input().strip().split()]
	r = [int(x) for x in input().strip().split()]
	cloud_start = [[y[i] - r[i], i] for i in range(m)]
	cloud_end = [[y[i] + r[i], i] for i in range(m)]
	result = maximumPeople(towns, cloud_start, cloud_end)
	print(result)
main()


import math
import os
import random
import re
import sys
from collections import defaultdict

def maximumPeople(towns, cloud_start, cloud_end):
	towns = sorted(towns)
	cloud_start = sorted(cloud_start)
	cloud_end = sorted(cloud_end)
	cloud_start_i = 0
	cloud_end_i = 0
	clouds = set()
	d = defaultdict(int)
	free = 0
	for town_i in range(len(towns)):
		town_x = towns[town_i][0]
		while cloud_start_i < len(cloud_start) and cloud_start[cloud_start_i][0] <= town_x:
			clouds.add(cloud_start[cloud_start_i][1])
			cloud_start_i += 1
		while cloud_end_i < len(cloud_end) and cloud_end[cloud_end_i][0] < town_x:
			clouds.remove(cloud_end[cloud_end_i][1])
			cloud_end_i += 1
		if len(clouds) == 1:
			towns[town_i][2] = list(clouds)[0]
			d[list(clouds)[0]] += towns[town_i][1]
		elif len(clouds) == 0:
			free += towns[town_i][1]
	return max(d.values(), default=0) + free

def main():
	n = int(input().strip())
	p = [int(x) for x in input().strip().split()]
	x = [int(x) for x in input().strip().split()]
	towns = [[xi, pi, -1] for (xi, pi) in zip(x, p)]
	m = int(input().strip())
	y = [int(x) for x in input().strip().split()]
	r = [int(x) for x in input().strip().split()]
	cloud_start = [[y[i] - r[i], i] for i in range(m)]
	cloud_end = [[y[i] + r[i], i] for i in range(m)]
	result = maximumPeople(towns, cloud_start, cloud_end)
	print(result)
main()