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!

Difficulty: interview

Starter code:

Solutions:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
#import io,os; input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline #for pypy
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))

# cook your dish here
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)


# cook your dish here
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))


    
    
#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,p[n-1]+p[i-1]-p[j])
       #     else:
        #        ssumi += max(0,p[n-1]-p[j])
        #else:
         #   if(i>=1):
          #      ssumi += max(p[j-1]-p[i],p[n-1]- p[j]+ p[i-1])
           # else:
            #    ssumi += max(p[j-1]-p[i],p[n-1]- p[j])
        #print(i,j,ssumi)
        #if(ssum < ssumi):
         #   ssum = ssumi
#print(max(ssum,maxa),maxa)

# cook your dish here
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))
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))


    
    
#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,p[n-1]+p[i-1]-p[j])
       #     else:
        #        ssumi += max(0,p[n-1]-p[j])
        #else:
         #   if(i>=1):
          #      ssumi += max(p[j-1]-p[i],p[n-1]- p[j]+ p[i-1])
           # else:
            #    ssumi += max(p[j-1]-p[i],p[n-1]- p[j])
        #print(i,j,ssumi)
        #if(ssum < ssumi):
         #   ssum = ssumi
#print(max(ssum,maxa),maxa)

# cook your dish here
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))
l = c.index(max(c[1:]))
m = d.index(max(d[:n-1]))
f = d.index(max(d))
k = d.index(max(d[1:]))
g = -10000000000
h = -10000000000
if(len(d[1:e])!=0):
    g = c[e]+ max(d[1:e]) + 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))


    
    
#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,p[n-1]+p[i-1]-p[j])
       #     else:
        #        ssumi += max(0,p[n-1]-p[j])
        #else:
         #   if(i>=1):
          #      ssumi += max(p[j-1]-p[i],p[n-1]- p[j]+ p[i-1])
           # else:
            #    ssumi += max(p[j-1]-p[i],p[n-1]- p[j])
        #print(i,j,ssumi)
        #if(ssum < ssumi):
         #   ssum = ssumi
#print(max(ssum,maxa),maxa)

# cook your dish here
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))
l = c.index(max(c[1:]))
m = d.index(max(d[:n-1]))
f = d.index(max(d))
k = d.index(max(d[1:]))
g = -10000000000
h = -10000000000
if(len(d[1:e])!=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))


    
    
#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,p[n-1]+p[i-1]-p[j])
       #     else:
        #        ssumi += max(0,p[n-1]-p[j])
        #else:
         #   if(i>=1):
          #      ssumi += max(p[j-1]-p[i],p[n-1]- p[j]+ p[i-1])
           # else:
            #    ssumi += max(p[j-1]-p[i],p[n-1]- p[j])
        #print(i,j,ssumi)
        #if(ssum < ssumi):
         #   ssum = ssumi
#print(max(ssum,maxa),maxa)

# cook your dish here
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])
        else:
            if(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])
#        print(i,j,ssumi)
        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)


#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
#import io,os; input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline #for pypy
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()))

B_prefix = [B[0]]
for i in range(1, N):
    B_prefix.append(B_prefix[-1] + B[i])
mxs = []

# for i == j
mxs.append(max(A))

# for i < j
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)

# for i > j
mxJ = A[0]
second_mx = mxJ + A[1] - B_prefix[1]
for i in range(1, N - 1):
    # print(second_mx, mxJ)
    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(*B_prefix)
print(max(mxs))



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])

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])

print(max(max(A),total_mx))

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)

# cook your dish here
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]
        else:
            if 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:
            #print("temp: ",temp,"i: ",i,"j: ",j,"C: ",C)
            answer = temp +0
print(answer)

# cook your dish here
'''
https://www.codechef.com/INOIPRAC/problems/INOI1501
'''

#inputFile = open('input.txt', 'r')
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)



# import all important libraries and inbuilt functions

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

# end of library import

# map system version faults
if sys.version_info[0] < 3:
    from builtins import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

# template of many functions used in competitive programming can add more later 
# based on need we will use this commonly.

# bfs in a graph
def bfs(adj,v): # a schema of bfs
    visited=[False]*(v+1);q=deque()
    while q:pass

# definition of vertex of a graph
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)

# most common list in a array of lists
def most_frequent(List):return Counter(List).most_common(1)[0][0]

# element with highest frequency
def most_common(List):return(mode(List))

#In number theory, the Chinese remainder theorem states that 
#if one knows the remainders of the Euclidean division of an integer n by 
#several integers, then one can determine uniquely the remainder of the 
#division of n by the product of these integers, under the condition 
#that the divisors are pairwise coprime.
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

# make a matrix
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

# input for a binary tree
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
    
# sieve of prime numbers    
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

#count setbits of a number.
def setBit(n):
    count=0
    while n!=0:n=n&(n-1);count+=1
    return count

# sum of digits of a number
def digitsSum(n):
    if n == 0:return 0
    r = 0
    while n > 0:r += n % 10;n //= 10
    return r

# ncr efficiently
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  # or / in Python 2

#factors of a number
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))))

#prime fators of a number
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

# maximum subarray sum use kadane's algorithm
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
 
#defining a LRU Cache
# where we can set values and get values based on our requirement
class LRUCache: 
	# initialising capacity 
	def __init__(self, capacity: int): 
		self.cache = OrderedDict() 
		self.capacity = capacity 

	# we return the value of the key 
	# that is queried in O(1) and return -1 if we 
	# don't find the key in out dict / cache. 
	# And also move the key to the end 
	# to show that it was recently used. 
	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] 

	# first, we add / update the key by conventional methods. 
	# And also move the key to the end to show that it was recently used. 
	# But here we will also check whether the length of our 
	# ordered dictionary has exceeded our capacity, 
	# If so we remove the first key (least recently used) 
	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)        
# can add more template functions here
    
# end of template functions

# To enable the file I/O i the below 2 lines are uncommented.
# read from in.txt if uncommented
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
# will print on Console if file I/O is not activated
#if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')

# inputs template
#for fast input we areusing sys.stdin
def inp(): return sys.stdin.readline().strip()

#for fast output, always take string
def out(var): sys.stdout.write(str(var))  

# cusom base input needed for the program
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()))

# end of inputs template

# common modulo values used in competitive programming
MOD = 998244353
mod = 10**9+7

# any particular user-defined functions for the code.
# can be written here.  
 
# end of any user-defined functions

# main functions for execution of the program.
def __starting_point():  
    # execute your program from here.
    # start your main code from here
        
    # Write your code here
    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)
    
    # end of main code
    # end of program

# This program is written by :
#   Shubham Gupta
#   B.Tech (2019-2023)
#   Computer Science and Engineering,
#   Department of EECS
#   Contact No:8431624358
#   Indian Institute of Technology(IIT),Bhilai
#   Sejbahar,
#   Datrenga,
#   Raipur,
#   Chhattisgarh
#   492015

#   THANK YOU FOR 
#YOUR KIND PATIENCE FOR READING THE PROGRAM.    
__starting_point()

# cook your dish here
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)

# cook your dish here
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())))
#print(b)
maxs = 0
#sumb = sum(b)
for i in range(0,len(a)):
    for j in range(0,len(a)):
        t = 0
        #print(i,j)
        if(i != j):
            t += a[i]
            t += a[j]
            k = i
            l = j
            if(i < j):
                t += (b[j-1] - b[i])
                #print(i,j,t)
                #print("i<j",t)
            elif(i > j):
                if(j > 0):
                    t += (b[-1]-b[i]+b[j-1])
                #print("i>j",t)
                else:
                    t += (b[-1]-b[i])
            else:
                pass
        else:
            t = a[i]
        if(maxs < t):
            maxs = t
            #print(maxs,i,j)
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
#print(pre)
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())))
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)

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]
        else:
            if 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)

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(1,n+1):
    for j in range(1,n+1):
        if i==j:
            flag=a[i-1]
        elif i<j:
            flag=a[i-1]+a[j-1]+(b[j-2]-b[i-1])
        else:
            if j==1:
                flag=a[i-1]+a[j-1]+(b[n-1]-b[i-1])
            else:
                flag=a[i-1]+a[j-1]+(b[n-1]-b[i-1])+b[j-2]
        ssum=max(ssum,flag)
print(ssum)