Finally, a basketball court has been opened in SIS, so Demid has decided to hold a basketball exercise session. $2 \cdot n$ students have come to Demid's exercise session, and he lined up them into two rows of the same size (there are exactly $n$ people in each row). Students are numbered from $1$ to $n$ in each row in order from left to right.

 [Image] 

Now Demid wants to choose a team to play basketball. He will choose players from left to right, and the index of each chosen player (excluding the first one taken) will be strictly greater than the index of the previously chosen player. To avoid giving preference to one of the rows, Demid chooses students in such a way that no consecutive chosen students belong to the same row. The first student can be chosen among all $2n$ students (there are no additional constraints), and a team can consist of any number of students. 

Demid thinks, that in order to compose a perfect team, he should choose students in such a way, that the total height of all chosen students is maximum possible. Help Demid to find the maximum possible total height of players in a team he can choose.


-----Input-----

The first line of the input contains a single integer $n$ ($1 \le n \le 10^5$) — the number of students in each row.

The second line of the input contains $n$ integers $h_{1, 1}, h_{1, 2}, \ldots, h_{1, n}$ ($1 \le h_{1, i} \le 10^9$), where $h_{1, i}$ is the height of the $i$-th student in the first row.

The third line of the input contains $n$ integers $h_{2, 1}, h_{2, 2}, \ldots, h_{2, n}$ ($1 \le h_{2, i} \le 10^9$), where $h_{2, i}$ is the height of the $i$-th student in the second row.


-----Output-----

Print a single integer — the maximum possible total height of players in a team Demid can choose.


-----Examples-----
Input
5
9 3 5 7 3
5 8 1 4 5

Output
29

Input
3
1 2 9
10 1 1

Output
19

Input
1
7
4

Output
7



-----Note-----

In the first example Demid can choose the following team as follows:  [Image] 

In the second example Demid can choose the following team as follows:  [Image]

Difficulty: interview

Starter code:

Solutions:
n = int(input())
h1 = list(map(int, input().split()))
h2 = list(map(int, input().split()))

r1 = r2 = 0
for i in range(n):
    r1, r2 = max(r1, r2 + h1[i]), max(r2, r1 + h2[i])

print(max(r1, r2))


n = int(input())
l = [[*map(int, input().split())], [*map(int, input().split())]]
dp = [0, 0]
for i in range(n):
    new_dp = dp[:]
    new_dp[0] = max(new_dp[0], dp[1] + l[0][i])
    new_dp[1] = max(new_dp[1], dp[0] + l[1][i])
    dp = new_dp
print(max(dp))

import sys

n = int(sys.stdin.readline().strip())
h1 = list(map(int, sys.stdin.readline().strip().split()))
h2 = list(map(int, sys.stdin.readline().strip().split()))
m1 = 0
n1 = h1[0]
m2 = 0
n2 = h2[0]
for i in range (1, n):
    m1, n1, m2, n2 = n1, h1[i] + max([m2, n2]), n2, h2[i] + max([m1, n1])
print(max([n1, n2]))

from sys import stdin, stdout, exit

n = int(stdin.readline())
top = list(map(int, stdin.readline().split()))
bot = list(map(int, stdin.readline().split()))

top_dp = [0]*(n+1)
bot_dp = [0]*(n+1)

for i in range(n):
    top_dp[i+1] = max(top_dp[i], bot_dp[i] + top[i])
    bot_dp[i+1] = max(bot_dp[i], top_dp[i] + bot[i])

ans = max(top_dp[n], bot_dp[n])
stdout.write(str(ans) + "\n")


from collections import defaultdict
n = int(input())


a = list(map(int,input().split()))
b = list(map(int,input().split()))

score = [[0 for x in range(n)]for _ in range(2)]


if n == 1:
    print (max(a[0],b[0]))
    return
elif n==2:
    print (max(a[0]+b[1],b[0]+a[1]))
    return


score[0][0] = a[0]
score[1][0] = b[0]
score[1][1] = a[0]+b[1]
score[0][1] = b[0]+a[1]


for x in range(2,n):
    # where it has been used
    score[0][x] = max(score[1][x-1],score[1][x-2]) + a[x]
    score[1][x] = max(score[0][x-1],score[0][x-2])+ b[x]
print (max(score[0][-1],score[1][-1]))

n = int(input())
a = [list(map(int, input().split())), list(map(int, input().split()))]
m = [a[0][-1], a[1][-1]]
for i in list(range(n - 1))[::-1]:
    m[0], m[1] = max(m[0], m[1] + a[0][i]), max(m[1], m[0] + a[1][i])
print(max(m[0], m[1]))


import sys
input = sys.stdin.readline

n=int(input())
H0=list(map(int,input().split()))
H1=list(map(int,input().split()))

DP0=[0]*(n+5)
DP1=[0]*(n+5)

DP0[0]=H0[0]
DP1[0]=H1[0]

for i in range(1,n):
    DP0[i]=max(DP1[i-1],DP1[i-2],DP0[i-2])+H0[i]
    DP1[i]=max(DP0[i-1],DP0[i-2],DP1[i-2])+H1[i]

print(max(max(DP0),max(DP1)))



import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n = getN()
anums = getList()
bnums = getList()

if n == 1:
    print(max(anums[0], bnums[0]))
    return

dp1 = [0 for i in range(n)]
dp2 = [0 for i in range(n)]

dp1[0] = anums[0]
dp1[1] = (anums[1] +  bnums[0])
dp2[0] = bnums[0]
dp2[1] = (bnums[1] + anums[0])
i = 0
for a, b in (list(zip(anums[2:], bnums[2:]))):
    dp1[i+2] = max(dp1[i], dp2[i+1], dp2[i]) + a
    dp2[i + 2] = max(dp2[i], dp1[i + 1], dp1[i]) + b
    i += 1
print(max(dp1[-1], dp1[-2], dp2[-1], dp2[-2]))
# print(dp1)
# print(dp2)



n = int(input())
r1 = list(map(int,input().split()))
r2 = list(map(int,input().split()))

# [i][0] sum when choosing r1 in pos
# [i][1] sum when choosing r2 in pos
# [i][2] sum when choosing nothing in pos
dp = [[0,0,0] for _ in range(n)] 
dp[0] = [r1[0],r2[0],0]
for i in range(1,n):
    last = dp[i-1]
    dp[i][0] = max(last[1], last[2]) + r1[i]
    dp[i][1] = max(last[0], last[2]) + r2[i]
    dp[i][2] = max(last[0], last[1])

print(max(dp[n-1]))


n = int(input())

a1 = list(map(int, input().split()))
a2 = list(map(int, input().split()))


m1 = [0]*n
m2 = [0]*n

m1[0] = a1[0]
m2[0] = a2[0]
if n != 1:
    m1[1] = m2[0] + a1[1]
    m2[1] = m1[0] + a2[1]

for i in range(2, n):
    m1[i] = max((m2[i-1]+a1[i], m1[i-2], m2[i-2]+a1[i]))
    m2[i] = max((m1[i - 1] + a2[i], m2[i - 2], m1[i-2] + a2[i]))

print(max(m1[-1], m2[-1]))

n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
ans=[a[n-1],b[n-1]]
bans=[0,0]
for i in range(n-2,-1,-1):
  bans[0] = max(a[i]+ans[1],ans[0])
  bans[1] = max(b[i]+ans[0],ans[1])
  ans[0]=bans[0]
  ans[1]=bans[1]
  bans[0]=0
  bans[1]=0
print(max(ans))


from math import*
n=int(input())
m1=list(map(int,input().split()))
m2=list(map(int,input().split()))
dp=[[0]*2 for i in range(n)]
if n==1:
    print(max(m1[0],m2[0]))
    return
if n==2:
    print(max(m1[0]+m2[1],m2[0]+m1[1]))
    return
dp[0][0]=m1[0]
dp[0][1]=m2[0]
dp[1][0]=m2[0]+m1[1]
dp[1][1]=m2[1]+m1[0]
for i in range(2,n):
    dp[i][0]=max(dp[i-1][1]+m1[i],dp[i-2][1]+m1[i])
    dp[i][1]=max(dp[i-1][0]+m2[i],dp[i-2][0]+m2[i])
print(max(dp[n-1]))


n = int(input())
h1 = list(map(int,input().split()))
h2 = list(map(int,input().split()))
if n > 1:
    h12 = [0] * n
    h22 = [0] * n
    h12[0] = h1[0]
    h22[0] = h2[0]
    h12[1] = max(h12[0],h22[0] + h1[1])
    h22[1] = max(h22[0],h12[0] + h2[1])
    for i in range(2,n):
        h12[i] = max(h12[i-1],h22[i-1] + h1[i])
        h22[i] = max(h22[i-1],h12[i-1] + h2[i])
        h12[i] = max(h12[i],h22[i-2] + h1[i])
        h22[i] = max(h22[i],h12[i-2] + h2[i])
    print(max(h12[-1],h22[-1]))
else:
    print(max(h1[0],h2[0]))


def gns():
    return list(map(int,input().split()))
n=int(input())
ps=[]
ps.append(gns())
ps.append(gns())
dp=[[0]*2 for i in range(n)]

def get(i,t):
    if i<0:
        return 0
    else:
        return dp[i][t]

ans=0
for i in range(n):
    for t in range(2):
        mx=max(get(i-1,1-t),get(i-2,1-t))
        dp[i][t]=mx+ps[t][i]
        ans=max(ans,dp[i][t])



print(ans)

from sys import stdin

n = int(stdin.readline())
h = [[], []]
h[0] = list(map(int, stdin.readline().split(' ')))
h[1] = list(map(int, stdin.readline().split(' ')))

dp = [[0 for i in range(n)], [0 for i in range(n)]]

dp[0][0] = h[0][0]
dp[1][0] = h[1][0]

for j in range(1, n):
   for i in [0, 1]:
      dp[i][j] = max(dp[i][j-1], h[i][j] + dp[i^1][j-1])

res = max(dp[0][n-1], dp[1][n-1])
print(res)


n=int(input())
l1=list(map(int,input().split()))
l2=list(map(int,input().split()))
m1,m2=0,0
for i in range(n-1,-1,-1):
    x1,x2=l1[i]+m2,l2[i]+m1
    if x1>m1:
        m1=x1
    if x2>m2:
        m2=x2
print(max(m1,m2))


n=int(input())
l=[[int(j) for j in input().split()] for i in range(2)]
d1=[0]*(n+1)
d2=[0]*(n+1)
d1[0]=l[0][0]
d2[0]=l[1][0]

for i in range(1,n):
    d1[i]=max(d1[i-1],d2[i-1]+l[0][i])
    d2[i]=max(d2[i-1],d1[i-1]+l[1][i])
print(max(d1[n-1],d2[n-1]))


n = int(input())
rows = []
rows.append(list(map(int, input().split())))
rows.append(list(map(int, input().split())))
best = [0, 0]
nextBest = [0, 0]
for k in range(n):
    nextBest[0] = max(best[1] + rows[0][k], best[0])
    nextBest[1] = max(best[0] + rows[1][k], best[1])
    best[0] = nextBest[0]
    best[1] = nextBest[1]
print(max(best))


n = int(input())
s1 = [int(i) for i in input().split()]
s2 = [int(i) for i in input().split()]
c1 = 0
c2 = 0
for i in range(n):
    temp1 = max(c1, c2+s1[i])
    temp2 = max(c2, c1+s2[i])
    c1 = temp1
    c2 = temp2
print(max(c1, c2))


''' CODED WITH LOVE BY SATYAM KUMAR '''

from sys import stdin, stdout
import cProfile, math
from collections import Counter,defaultdict,deque
from bisect import bisect_left,bisect,bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
sys.setrecursionlimit(10**6) # max depth of recursion
threading.stack_size(2**27)  # new thread will get stack of such size
fac_warmup = False
printHeap = str()
memory_constrained = False
P = 10**9+7
import sys

class merge_find:
    def __init__(self,n):
        self.parent = list(range(n))
        self.size = [1]*n
        self.num_sets = n
        self.lista = [[_] for _ in range(n)]
    def find(self,a):
        to_update = []
        while a != self.parent[a]:
            to_update.append(a)
            a = self.parent[a]
        for b in to_update:
            self.parent[b] = a
        return self.parent[a]
    def merge(self,a,b):
        a = self.find(a)
        b = self.find(b)
        if a==b:
            return
        if self.size[a]<self.size[b]:
            a,b = b,a
        self.num_sets -= 1
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.lista[a] += self.lista[b]
    def set_size(self, a):
        return self.size[self.find(a)]
    def __len__(self):
        return self.num_sets

def display(string_to_print):
    stdout.write(str(string_to_print) + "\n")

def primeFactors(n): #n**0.5 complex 
    factors = dict()
    for i in range(2,math.ceil(math.sqrt(n))+1):  
        while n % i== 0: 
            if i in factors:
                factors[i]+=1
            else: factors[i]=1
            n = n // i 
    if n>2:
        factors[n]=1
    return (factors)

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

def fibonacci_modP(n,MOD):
    if n<2: return 1
    #print (n,MOD)
    return (cached_fn(fibonacci_modP, (n+1)//2, MOD)*cached_fn(fibonacci_modP, n//2, MOD) + cached_fn(fibonacci_modP, (n-1) // 2, MOD)*cached_fn(fibonacci_modP, (n-2) // 2, MOD)) % MOD

def factorial_modP_Wilson(n , p): 
    if (p <= n): 
        return 0
    res = (p - 1) 
    for i in range (n + 1, p): 
        res = (res * cached_fn(InverseEuler,i, p)) % p 
    return res 

def binary(n,digits = 20):
    b = bin(n)[2:]
    b = '0'*(digits-len(b))+b
    return b

def isprime(n):
    """Returns True if n is prime."""
    if n < 4:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w
    return True

def generate_primes(n):
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * 2, n+1, p): 
                prime[i] = False
        p += 1
    return prime

factorial_modP = []
def warm_up_fac(MOD):
    nonlocal factorial_modP,fac_warmup
    if fac_warmup: return
    factorial_modP= [1 for _ in range(fac_warmup_size+1)]
    for i in range(2,fac_warmup_size):
        factorial_modP[i]= (factorial_modP[i-1]*i) % MOD
    fac_warmup = True

def InverseEuler(n,MOD):
    return pow(n,MOD-2,MOD)

def nCr(n, r, MOD):
    nonlocal fac_warmup,factorial_modP
    if not fac_warmup:
        warm_up_fac(MOD)
        fac_warmup = True
    return (factorial_modP[n]*((pow(factorial_modP[r], MOD-2, MOD) * pow(factorial_modP[n-r], MOD-2, MOD)) % MOD)) % MOD

def test_print(*args):
    if testingMode:
        print(args)

def display_list(list1, sep=" "):
    stdout.write(sep.join(map(str, list1)) + "\n")

def display_2D_list(li):
    for i in li:
        print(i)
def prefix_sum(li):
    sm = 0
    res = []
    for i in li:
        sm+=i
        res.append(sm)
    return res

def get_int():
    return int(stdin.readline().strip())

def get_tuple():
    return map(int, stdin.readline().split())

def get_list():
    return list(map(int, stdin.readline().split()))
import heapq,itertools
pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>' 
def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heapq.heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heapq.heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')
memory = dict()
def clear_cache():
    nonlocal memory
    memory = dict()
def cached_fn(fn, *args):
    nonlocal memory
    if args in memory:
        return memory[args]
    else:
        result = fn(*args)
        memory[args] = result
        return result

def ncr (n,r):
    return math.factorial(n)/(math.factorial(n-r)*math.factorial(r))
def binary_serach(i,li):
    #print("Search for ",i)
    fn = lambda x: li[x]-x//i
    x = -1
    b = len(li)
    while b>=1:
        #print(b,x)
        while b+x<len(li) and fn(b+x)>0: #Change this condition 2 to whatever you like
            x+=b
        b=b//2
    return x

# -------------------------------------------------------------- MAIN PROGRAM
TestCases = False
testingMode = False
fac_warmup_size = 10**5+100
optimiseForReccursion = False #Can not be used clubbed with TestCases # WHen using recursive functions, use Python 3
from math import factorial

def main():
    n = get_int()
    a = get_list()
    b = get_list()
    u = [0,0]
    l = [0,0]
    for i in range(n):
        u.append(max(l[-1],l[-2],u[-2])+b[i])
        l.append(max(u[-2],u[-3],l[-2])+a[i])
    print(max(u[-1],l[-1]))

# --------------------------------------------------------------------- END=


if TestCases: 
    for i in range(get_int()): 
        cProfile.run('main()') if testingMode else main() 
else: (cProfile.run('main()') if testingMode else main()) if not optimiseForReccursion else threading.Thread(target=main).start()

n = int( input() )
l = [ list( map( int, input().split() )), list( map( int, input().split())) ]
m = [ 0, 0 ]
for i in range(n-1, -1, -1):
    mm = [ 0, 0 ]
    for j in range(2):
        l[ j ][ i ] += m[ j^1 ]
        mm[ j ] = max( m[ j ], l[ j ][ i ] )
    m = mm

print( max( m ) )


n = int(input())
l1 = [0, 0] + list(map(int, input().split()))
l2 = [0, 0] + list(map(int, input().split()))
ans1 = [0] * (n + 3)
ans2 = [0] * (n + 3)
for i in range(2, n + 2):
    ans1[i] = max(ans2[i - 1], ans2[i - 2]) + l1[i]
    ans2[i] = max(ans1[i - 1], ans1[i - 2]) + l2[i]
print(max(ans1[n + 1], ans2[n + 1]))

n = int(input())
first = list(map(int, input().split()))
second = list(map(int, input().split()))

dp_first = [0] * n
dp_second = [0] * n

dp_first[0] = first[0]
dp_second[0] = second[0]

for i in range(1, n):
    dp_first[i] = max(dp_first[i - 1], first[i] + dp_second[i - 1], first[i] + dp_second[i - 2] if i >= 2 else 0)
    dp_second[i] = max(dp_second[i - 1], second[i] + dp_first[i - 1], second[i] + dp_first[i - 2] if i >= 2 else 0)

print(max(dp_first[-1], dp_second[-1]))