Indian National Olympiad in Informatics 2015
In this problem you are given two lists of N integers, a1, a2, ..., aN and b1, b2, ... bN. For any pair (i, j) with i, j ϵ {1, 2, ..., N} we define the segment from i to j, written as [i, j], to be i, i + 1, ..., j if i ≤ j and i, i + 1, ..., N, 1, 2, ...,j if i > j. Thus if N = 5 then the [2, 4] = {2, 3, 4} and [4, 2] = {4, 5, 1, 2}.
With each segment [i, j] we associate a special sum SSum[i, j] as follows:
- SSum[i, i] = ai.
- If i ≠ j then, 

The positions i and j contribute ai and aj, respectively, to the sum while every other position k in [i, j] contributes bk.
Suppose N = 5 and that the two given sequences are as follows:
i
1
2
3
4
5
ai
2
3
2
3
1
bi
3
4
4
6
3

Then, SSum[1, 1] = 2, SSum[2, 4] = 3 + 4 + 3 = 10 and SSum[4, 2] = 3 + 3 + 3 + 3 = 12. Your aim is to compute the maximum value of SSum[i, j] over all segments [i, j]. In this example you can verify that this value is 18 (SSum[2, 1] = 18).

-----Input format-----
- The first line contains a single positive integer N.
- This is followed by a line containing N integers giving the values of the ais and this is followed by a line containing N integers giving the values of the bis.

-----Output format-----
A single integer in a single line giving the maximum possible special segment sum.
Note: The final value may not fit in a 32 bit integer. Use variables of an appropriate type to store and manipulate this value (long long in C/C++, long in Java).

-----Test Data-----
You may assume that -109 ≤ ai, bi ≤ 109.
Subtask 1 (10 Marks) 1 ≤ N ≤ 3000.
Subtask 2 (20 Marks) 1 ≤ N ≤ 106 and ai = bi for all 1 ≤ i ≤ N.
Subtask 3 (30 Marks) 3 ≤ N ≤106. Further a1 = b1 = aN = bN = -109 and for each
1 < k < N we have -999 ≤ ak, bk ≤ 999.
Subtask 4 (40 Marks) 1 ≤ N ≤ 106.

-----Example-----
Here is the sample input and output corresponding to the example above:

-----Sample input-----
5
2 3 2 3 1
3 4 4 6 3

-----Sample output-----
18

Note: Your program should not print anything other than what is specified in the output format. Please remove all diagnostic print statements before making your final submission. A program with extraneous output will be treated as incorrect!

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys
input = sys.stdin.readline
(inp, ip) = (lambda : int(input()), lambda : [int(w) for w in input().split()])
from collections import deque

def getmax(x, n, k):
	mx = []
	dq = deque()
	for i in range(k):
		while dq and x[i] >= x[dq[-1]]:
			dq.pop()
		dq.append(i)
	mx.append(x[dq[0]])
	for i in range(k, n):
		while dq and dq[0] <= i - k:
			dq.popleft()
		while dq and x[i] >= x[dq[-1]]:
			dq.pop()
		dq.append(i)
		mx.append(x[dq[0]])
	return mx
n = inp()
m = n + n
A = ip()
B = ip()
A += A
B += B
pre = [0] * (m + 1)
for i in range(1, m + 1):
	pre[i] += pre[i - 1] + B[i - 1]
plus = [0] * m
minus = [0] * m
for i in range(m):
	plus[i] = A[i] + pre[i]
	minus[i] = A[i] - pre[i + 1]
a = getmax(plus, m, n - 1)
ans = float('-inf')
for i in range(n):
	ans = max(ans, minus[i] + a[i + 1])
print(max(ans, *A))


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
p = [b[0]]
p1 = [a[0]]
p2 = [a[0] - b[0]]
for i in range(1, n):
	p.append(b[i] + p[i - 1])
for i in range(1, n):
	p1.append(max(p1[i - 1], a[i] + p[i - 1]))
for i in range(1, n):
	p2.append(max(p2[i - 1], a[i] - p[i]))
maxi = max(a)
for i in range(1, n):
	maxi = max(maxi, a[i] + p[i - 1] + p2[i - 1])
	maxi = max(maxi, p[n - 1] + a[i] - p[i] + p1[i - 1])
print(maxi)


n = int(input())
a = list(map(int, input().strip().split()))
b = list(map(int, input().strip().split()))
p = [b[0]]
c = []
d = []
for i in range(1, n):
	p.append(p[i - 1] + b[i])
for i in range(n):
	c.append(a[i] - p[i])
	d.append(a[i] + p[i - 1])
e = c.index(max(c[:n - 1]))
l = c.index(max(c[2:]))
m = d.index(max(d[1:n - 1]))
f = d.index(max(d))
k = d.index(max(d[1:]))
g = -10000000000
h = -10000000000
if len(d[1:l]) != 0:
	g = c[l] + max(d[1:l]) + p[n - 1]
if len(c[k + 1:]) != 0:
	h = d[k] + max(c[k + 1:]) + p[n - 1]
s1 = max(g, h, max(c[1:]) + a[0] + p[n - 1])
h = -10000000000
g = d[k] + max(c[:k])
if len(d[e + 1:]) != 0:
	h = c[e] + max(d[e + 1:])
s2 = max(g, h)
print(max(max(a), s1, s2))


n = int(input())
a = list(map(int, input().strip().split()))
b = list(map(int, input().strip().split()))
ssum = 0
prefx = [b[0]]
for i in range(1, n):
	c = prefx[i - 1] + b[i]
	prefx.append(c)
maxa = a[n - 1]
for i in range(n - 1):
	maxa = max(a[i], maxa)
	for j in range(i + 1, n):
		ssumi = a[i] + a[j]
		if j - i == 1:
			if i >= 1:
				ssumi += max(0, prefx[n - 1] + prefx[i - 1] - prefx[j])
			else:
				ssumi += max(0, prefx[n - 1] - prefx[j])
		elif i >= 1:
			ssumi += max(prefx[j - 1] - prefx[i], prefx[n - 1] - prefx[j] + prefx[i - 1])
		else:
			ssumi += max(prefx[j - 1] - prefx[i], prefx[n - 1] - prefx[j])
		if ssum < ssumi:
			ssum = ssumi
print(max(ssum, maxa))


n = int(input())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
ps = [0] * (n + 1)
for i in range(1, n + 1):
	ps[i] = ps[i - 1] + b[i]
ms = [float('-inf')] * (n + 1)
for i in range(1, n + 1):
	ms[i] = max(ms[i - 1], a[i] - ps[i])
ns = [float('-inf')] * (n + 1)
ns[n] = a[n] - ps[n]
for i in range(n - 1, 0, -1):
	ns[i] = max(ns[i + 1], a[i] - ps[i])
maxi = max(a)
for j in range(2, n + 1):
	maxi = max(maxi, a[j] + ps[j - 1] + ms[j - 1])
for j in range(1, n):
	maxi = max(maxi, a[j] + ps[n] + ps[j - 1] + ns[j + 1])
print(maxi)


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
B_prefix = [B[0]]
for i in range(1, N):
	B_prefix.append(B_prefix[-1] + B[i])
mxs = []
mxs.append(max(A))
mxI = A[0] - B_prefix[0]
total_mx = mxI + A[1] + B_prefix[0]
for i in range(1, N):
	mxI = max(mxI, A[i - 1] - B_prefix[i - 1])
	total_mx = max(total_mx, mxI + A[i] + B_prefix[i - 1])
mxs.append(total_mx)
mxJ = A[0]
second_mx = mxJ + A[1] - B_prefix[1]
for i in range(1, N - 1):
	mxJ = max(mxJ, A[i] + B_prefix[i - 1])
	second_mx = max(second_mx, mxJ + A[i + 1] - B_prefix[i + 1])
mxs.append(second_mx + B_prefix[-1])
print(max(mxs))


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.insert(0, 0)
b.insert(0, 0)
prefixsum = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
	prefixsum[i] = prefixsum[i - 1] + b[i]

def ssum(i, j):
	if i < j:
		return a[i] + a[j] + prefixsum[j - 1] - prefixsum[i]
	elif i > j:
		return a[i] + a[j] + prefixsum[n] - (prefixsum[i] - prefixsum[j - 1])
	else:
		return a[i]
ans = float('-inf')
for i in range(1, n + 1):
	for j in range(1, n + 1):
		ans = max(ans, ssum(i, j))
print(ans)


from itertools import accumulate
import copy
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = copy.deepcopy(B)
for i in range(1, len(C)):
	C[i] += C[i - 1]
answer = 0
temp = 0
for i in range(N):
	for j in range(N):
		temp = 0
		if i == j:
			temp = A[i]
		elif i < j:
			temp += A[i] + A[j] + C[j - 1] - C[i]
		else:
			temp += A[i] + A[j] + C[N - 1] - C[i] + C[j] - B[j]
		if temp > answer:
			answer = temp + 0
print(answer)


n = int(input())
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
ans = a[0]
diff = [0] * n
presumb = [0] * n
presumb[0] = b[0]
for i in range(1, n):
	presumb[i] = presumb[i - 1] + b[i]
mx = a[0] - presumb[0]
diff[0] = mx
for i in range(1, n):
	diff[i] = max(diff[i - 1], a[i] - presumb[i])
for i in range(1, n):
	ans = max(ans, a[i] + presumb[i - 1] + diff[i - 1])
halfmaxwraparound = [0] * n
halfmaxwraparound[0] = a[0]
totalarraysumb = presumb[n - 1]
for i in range(1, n):
	halfmaxwraparound[i] = max(halfmaxwraparound[i - 1], a[i] + presumb[i - 1])
for i in range(1, n):
	ans = max(ans, halfmaxwraparound[i - 1] + a[i] + totalarraysumb - presumb[i])
print(ans)


from fractions import Fraction
import numpy as np
import sys, bisect, copyreg, copy, statistics, os
from math import *
from collections import Counter, defaultdict, deque, OrderedDict
from itertools import combinations, permutations, accumulate, groupby
from numpy.linalg import matrix_power as mp
from bisect import bisect_left, bisect_right, bisect, insort, insort_left, insort_right
from statistics import mode
from functools import reduce, cmp_to_key
from io import BytesIO, IOBase
from scipy.spatial import ConvexHull
from heapq import *
from decimal import *
from queue import Queue, PriorityQueue
from re import sub, subn
if sys.version_info[0] < 3:
	from builtins import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def bfs(adj, v):
	visited = [False] * (v + 1)
	q = deque()
	while q:
		pass

def graph(vertex):
	return [[] for i in range(vertex + 1)]

def powermodulo(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def lcm(a, b):
	return a * b // gcd(a, b)

def most_frequent(List):
	return Counter(List).most_common(1)[0][0]

def most_common(List):
	return mode(List)

def chinese_remainder(a, p):
	prod = reduce(op.mul, p, 1)
	x = [prod // pi for pi in p]
	return sum((a[i] * powermodulo(x[i], p[i] - 2, p[i]) * x[i] for i in range(len(a)))) % prod

def createMatrix(rowCount, colCount, dataList):
	mat = []
	for i in range(rowCount):
		rowList = []
		for j in range(colCount):
			if dataList[j] not in mat:
				rowList.append(dataList[j])
		mat.append(rowList)
	return mat

def readTree():
	v = int(inp())
	adj = [set() for i in range(v + 1)]
	for i in range(v - 1):
		(u1, u2) = In()
		adj[u1].add(u2)
		adj[u2].add(u1)
	return (adj, v)

def sieve():
	li = [True] * 1000001
	(li[0], li[1]) = (False, False)
	prime = []
	for i in range(2, len(li), 1):
		if li[i] == True:
			for j in range(i * i, len(li), i):
				li[j] = False
	for i in range(1000001):
		if li[i] == True:
			prime.append(i)
	return prime

def setBit(n):
	count = 0
	while n != 0:
		n = n & n - 1
		count += 1
	return count

def digitsSum(n):
	if n == 0:
		return 0
	r = 0
	while n > 0:
		r += n % 10
		n //= 10
	return r

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, list(range(n, n - r, -1)), 1)
	denom = reduce(op.mul, list(range(1, r + 1)), 1)
	return numer // denom

def factors(n):
	return list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return len(set(factors))

def prefixSum(arr):
	for i in range(1, len(arr)):
		arr[i] = arr[i] + arr[i - 1]
	return arr

def binomial_coefficient(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0

def powerOfK(k, max):
	if k == 1:
		return [1]
	if k == -1:
		return [-1, 1]
	result = []
	n = 1
	while n <= max:
		result.append(n)
		n *= k
	return result

def kadane(a, size):
	max_so_far = 0
	max_ending_here = 0
	for i in range(0, size):
		max_ending_here = max_ending_here + a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
		if max_ending_here < 0:
			max_ending_here = 0
	return max_so_far

def divisors(n):
	result = []
	for i in range(1, ceil(sqrt(n)) + 1):
		if n % i == 0:
			if n / i == i:
				result.append(i)
			else:
				result.append(i)
				result.append(n / i)
	return result

def sumtilln(n):
	return n * (n + 1) // 2

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, ceil(sqrt(n)) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def isPowerOf2(n):
	while n % 2 == 0:
		n //= 2
	return True if n == 1 else False

def power2(n):
	k = 0
	while n % 2 == 0:
		k += 1
		n //= 2
	return k

def sqsum(n):
	return n * (n + 1) * (2 * n + 1) // 6

def cusum(n):
	return sumn(n) ** 2

def pa(a):
	for i in range(len(a)):
		print(a[i], end=' ')
	print()

def pm(a, rown, coln):
	for i in range(rown):
		for j in range(coln):
			print(a[i][j], end=' ')
		print()

def pmasstring(a, rown, coln):
	for i in range(rown):
		for j in range(coln):
			print(a[i][j], end='')
		print()

def isPerfectSquare(n):
	return pow(floor(sqrt(n)), 2) == n

def nC2(n, m):
	return n * (n - 1) // 2 % m

def modInverse(n, p):
	return powermodulo(n, p - 2, p)

def ncrmodp(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * powermodulo(den, p - 2, p) % p

def reverse(string):
	return ''.join(reversed(string))

def listtostr(s):
	return ' '.join([str(elem) for elem in s])

def binarySearch(arr, l, r, x):
	while l <= r:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	return -1

def isarrayodd(a):
	r = True
	for i in range(len(a)):
		if a[i] % 2 == 0:
			r = False
			break
	return r

def isPalindrome(s):
	return s == s[::-1]

def gt(x, h, c, t):
	return (x * h + (x - 1) * c) / (2 * x - 1)

def CountFrequency(my_list):
	freq = {}
	for item in my_list:
		freq[item] = freq[item] + 1 if item in freq else 1
	return freq

def CountFrequencyasPair(my_list1, my_list2, freq):
	for item in my_list1:
		freq[item][0] = freq[item][0] + 1 if item in freq else 1
	for item in my_list2:
		freq[item][1] = freq[item][1] + 1 if item in freq else 1
	return freq

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			(count, left) = (mid + 1, mid + 1)
		else:
			right = mid - 1
	return count

def primes(n):
	(sieve, l) = ([True] * (n + 1), [])
	for p in range(2, n + 1):
		if sieve[p]:
			l.append(p)
			for i in range(p, n + 1, p):
				sieve[i] = False
	return l

def Next_Greater_Element_for_all_in_array(arr):
	(s, n, reta, retb) = (list(), len(arr), [], [])
	arr1 = [list([0, i]) for i in range(n)]
	for i in range(n - 1, -1, -1):
		while len(s) > 0 and s[-1][0] <= arr[i]:
			s.pop()
		if len(s) == 0:
			arr1[i][0] = -1
		else:
			arr1[i][0] = s[-1]
		s.append(list([arr[i], i]))
	for i in range(n):
		reta.append(list([arr[i], i]))
		retb.append(arr1[i][0])
	return (reta, retb)

def polygonArea(X, Y, n):
	area = 0.0
	j = n - 1
	for i in range(n):
		area += (X[j] + X[i]) * (Y[j] - Y[i])
		j = i
	return abs(area / 2.0)

def merge(a, b):
	ans = defaultdict(int)
	for i in a:
		ans[i] += a[i]
	for i in b:
		ans[i] += b[i]
	return ans

class LRUCache:

	def __init__(self, capacity: int):
		self.cache = OrderedDict()
		self.capacity = capacity

	def get(self, key: int) -> int:
		if key not in self.cache:
			return -1
		else:
			self.cache.move_to_end(key)
			return self.cache[key]

	def put(self, key: int, value: int) -> None:
		self.cache[key] = value
		self.cache.move_to_end(key)
		if len(self.cache) > self.capacity:
			self.cache.popitem(last=False)

class segtree:

	def __init__(self, n):
		self.m = 1
		while self.m < n:
			self.m *= 2
		self.data = [0] * (2 * self.m)

	def __setitem__(self, i, x):
		x = +(x != 1)
		i += self.m
		self.data[i] = x
		i >>= 1
		while i:
			self.data[i] = self.data[2 * i] + self.data[2 * i + 1]
			i >>= 1

	def __call__(self, l, r):
		l += self.m
		r += self.m
		s = 0
		while l < r:
			if l & 1:
				s += self.data[l]
				l += 1
			if r & 1:
				r -= 1
				s += self.data[r]
			l >>= 1
			r >>= 1
		return s

class FenwickTree:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def update(self, x, d):
		while x <= self.n:
			self.bit[x] += d
			x += x & -x

	def query(self, x):
		res = 0
		while x > 0:
			res += self.bit[x]
			x -= x & -x
		return res

	def range_query(self, l, r):
		return self.query(r) - self.query(l - 1)
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')

def inp():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(str(var))

def I():
	return inp()

def II():
	return int(inp())

def FI():
	return float(inp())

def SI():
	return list(str(inp()))

def MI():
	return map(int, inp().split())

def LI():
	return list(MI())

def SLI():
	return sorted(LI())

def MF():
	return map(float, inp().split())

def LF():
	return list(MF())

def SLF():
	return sorted(LF())
MOD = 998244353
mod = 10 ** 9 + 7

def __starting_point():
	n = II()
	(a, b) = (LI(), LI())
	(pb, pr) = ([], 0)
	for i in b:
		pr += i
		pb.append(pr)
	(mi, mj) = ([0] * n, [0] * n)
	mj[0] = a[0] - pb[0]
	for i in range(1, n):
		mj[i] = max(mj[i - 1], a[i] - pb[i])
	mi[0] = a[0]
	for i in range(1, n):
		mi[i] = max(mi[i - 1], a[i] + pb[i - 1])
	ans = a[0]
	for i in range(1, n):
		ans = max(ans, a[i], a[i] + pb[i - 1] + mj[i - 1], a[i] + pb[n - 1] - pb[i] + mi[i - 1])
	print(ans)
__starting_point()


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
res = 0
prev = [0] * 1000006
summ = [0] * 1000006
diff = [0] * 1000006
prev[0] = b[0]
for i in range(n):
	res = max(res, a[i])
for i in range(1, n):
	prev[i] = b[i] + prev[i - 1]
summ[0] = a[0]
diff[0] = a[0] = prev[0]
for i in range(n):
	diff[i] = max(diff[i - 1], a[i] - prev[i])
for i in range(n):
	summ[i] = max(summ[i], a[i] + prev[i - 1])
for i in range(n):
	res = max(res, a[i] + prev[i - 1] + diff[i - 1])
for i in range(n):
	res = max(res, a[i] + prev[n - 1] + summ[i - 1] - prev[i])
print(res)


import sys
read = sys.stdin.readline
n = int(read())
a = list(map(int, read().split()))
b = list(map(int, read().split()))
presb = []
pref = 0
for ele in b:
	pref += ele
	presb.append(pref)
maxj = [0] * n
maxi = [0] * n
maxj[0] = a[0] - presb[0]
for i in range(1, n):
	maxj[i] = max(maxj[i - 1], a[i] - presb[i])
maxi[0] = a[0]
for j in range(1, n):
	maxi[j] = max(maxi[j - 1], a[j] + presb[j - 1])
ans = a[0]
for i in range(1, n):
	ans = max(ans, a[i], a[i] + presb[i - 1] + maxj[i - 1], a[i] + presb[n - 1] - presb[i] + maxi[i - 1])
print(ans)


import sys
from itertools import accumulate
read = sys.stdin.readline
n = int(read())
a = tuple(map(int, read().split()))
b = tuple(accumulate(map(int, read().split())))
maxs = 0
for i in range(0, len(a)):
	for j in range(0, len(a)):
		t = 0
		if i != j:
			t += a[i]
			t += a[j]
			k = i
			l = j
			if i < j:
				t += b[j - 1] - b[i]
			elif i > j:
				if j > 0:
					t += b[-1] - b[i] + b[j - 1]
				else:
					t += b[-1] - b[i]
			else:
				pass
		else:
			t = a[i]
		if maxs < t:
			maxs = t
print(maxs)


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a1 = [0] * 100006
maximum = 0
prev = [0] * 100006
diff = [0] * 100006
summ = [0] * 100006
prev[0] = b[0]
for i in a:
	maximum = max(maximum, i)
for j in range(n):
	prev[j] = b[j] + prev[j - 1]
diff[0] = a[0] - prev[0]
summ[0] = a[0]
for i in range(1, n):
	diff[i] = max(diff[i - 1], a[i] - prev[i])
for i in range(1, n):
	summ[i] = max(summ[i - 1], a[i] + prev[i - 1])
for i in range(1, n):
	maximum = max(maximum, a[i] + prev[i - 1] + diff[i - 1])
for i in range(1, n):
	maximum = max(maximum, a[i] + prev[n - 1] - prev[i] + summ[i - 1])
print(maximum)


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a1 = [0] * 100006
maximum = 0
prev = [0] * 100006
prev[0] = b[0]
for j in range(n):
	prev[j] = b[j] + prev[j - 1]
for i in range(0, n):
	for j in range(0, n):
		if i == j:
			maximum = max(maximum, a[i])
		elif i < j:
			maximum = max(maximum, a[i] + a[j] + prev[j - 1] - prev[i])
		else:
			maximum = max(maximum, a[i] + a[j] + prev[n - 1] + prev[j - 1] - prev[i])
print(maximum)


from itertools import accumulate
n = int(input())
a = tuple(map(int, input().split()))
b = tuple(accumulate(map(int, input().split())))
dpf = [0] * n
dpf[0] = a[0] - b[0]
for i in range(1, n):
	dpf[i] = max(dpf[i - 1], a[i] - b[i])
dpb = [0] * n
dpb[0] = a[0]
for i in range(1, n):
	dpb[i] = max(dpb[i - 1], a[i] + b[i - 1])
ans = a[0]
for i in range(1, n):
	ans = max(ans, a[i], a[i] + b[i - 1] + dpf[i - 1], a[i] + b[n - 1] - b[i] + dpb[i - 1])
print(ans)


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
pre = [0]
for i in range(n):
	pre.append(pre[-1] + b[i])
maxi = 0
for i in range(n):
	for j in range(n):
		if i == j:
			ans = a[i]
		elif i < j:
			ans = a[i] + a[j] + pre[j] - pre[i + 1]
		else:
			ans = a[i] + a[j] + pre[n] - pre[i + 1] + pre[j]
		maxi = max(ans, maxi)
print(maxi)


from itertools import accumulate
n = int(input())
a = tuple(map(int, input().split()))
b = tuple(accumulate(map(int, input().split())))
ssum = 0
for i in range(0, n):
	for j in range(i, n):
		if i == j:
			flag = a[i]
		elif i == 0:
			flag = a[i] + a[j] + max(b[j - 1] - b[i], b[n - 1] - b[j])
		else:
			flag = a[i] + a[j] + max(b[j - 1] - b[i], b[n - 1] - b[j] + b[i - 1])
		ssum = max(ssum, flag)
print(ssum)