Problem:
 Score : 100 points    Problem Statement Taro's summer vacation starts tomorrow, and he has decided to make plans for it now.  The vacation consists of N days.
For each i ( 1 \leq i \leq N ), Taro will choose one of the following activities and do it on the i -th day:   A: Swim in the sea. Gain a_i points of happiness.  B: Catch bugs in the mountains. Gain b_i points of happiness.  C: Do homework at home. Gain c_i points of happiness.   As Taro gets bored easily, he cannot do the same activities for two or more consecutive days.  Find the maximum possible total points of happiness that Taro gains.      Constraints  All values in input are integers.  1 \leq N \leq 10^5  1 \leq a_i, b_i, c_i \leq 10^4         Input Input is given from Standard Input in the following format:  N  a_1  b_1  c_1  a_2  b_2  c_2  :  a_N  b_N  c_N       Output Print the maximum possible total points of happiness that Taro gains.        Sample Input 1 3
10 40 70
20 50 80
30 60 90      Sample Output 1 210  If Taro does activities in the order C, B, C, he will gain 70 + 50 + 90 = 210 points of happiness.       Sample Input 2 1
100 10 1      Sample Output 2 100       Sample Input 3 7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1      Sample Output 3 46  Taro should do activities in the order C, A, B, A, C, B, A.

Solution (Python):
n=int(input())
a=[0]
b=[0]
c=[0]
for i in range(n):
    A,B,C=map(int, input().split())
    a.append(A)
    b.append(B)
    c.append(C)

dp=[[10**10,10**10,10**10] for i in range(n+1)]

dp[0][0]=0
dp[0][1]=0
dp[0][2]=0

dp[1][0]=a[1]
dp[1][1]=b[1]
dp[1][2]=c[1]

for i in range(2,n+1):
    dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][2]+a[i])
    dp[i][1]=max(dp[i-1][0]+b[i],dp[i-1][2]+b[i])
    dp[i][2]=max(dp[i-1][1]+c[i],dp[i-1][0]+c[i])

print(max(dp[n]))

Solution (Python):

import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

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


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    n = int(input())
    
    
    d1 = [0]*n
    d2 = [0]*n
    d3 = [0]*n
    for i in range(n):
        x, y, z = map(int, input().split())
        if not i:
            d1[i] = x
            d2[i] = y
            d3[i] = z
            continue

        d1[i] = max(d2[i-1], d3[i-1]) + x
        d2[i] = max(d1[i-1], d3[i-1]) + y
        d3[i] = max(d1[i-1], d2[i-1]) + z

    print(max(d1[-1], d2[-1], d3[-1]))

Solution (Python):
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
a,b,c = [list(i) for i in zip(*l)]
dp = [[0,0,0] for i in range(n+1)]
for i in range(n):
    dp[i+1][0] = max(dp[i][1]+a[i],dp[i][2]+a[i])
    dp[i+1][1] = max(dp[i][0]+b[i],dp[i][2]+b[i])
    dp[i+1][2] = max(dp[i][0]+c[i],dp[i][1]+c[i])
print(max(dp[-1]))

Solution (Python):
n = int(input())
l = [list(map(int, input().split())) for i in range(n)]
a, b, c = [list(i) for i in zip(*l)]
dp = [[0, 0, 0] for i in range(n+1)]
for i in range(n):
    dp[i+1][0] = max(dp[i][1]+a[i], dp[i][2]+a[i])
    dp[i+1][1] = max(dp[i][0]+b[i], dp[i][2]+b[i])
    dp[i+1][2] = max(dp[i][0]+c[i], dp[i][1]+c[i])
print(max(dp[-1][0], dp[-1][1], dp[-1][2]))

Solution (Python):
n = int(input())

dp = [[0]*3 for i in range(n+1)]
a = []

for i in range(n):
    a.append(list(map(int,input().split())))

for i in range(n):
    for j in range(3):
        for k in range(3):
            if j==k:
                continue
            dp[i+1][j] = max(dp[i+1][j],dp[i][k] + a[i][j])

print(max(dp[n]))

Solution (Python):

def main():
    N = int(input())
    happiness = [list(map(int, input().split())) for _ in range(N)]

    dp = [0, 0, 0]
    for a, b, c in happiness:
        dp = [max(dp[1], dp[2]) + a,
              max(dp[0], dp[2]) + b,
              max(dp[0], dp[1]) + c]
    print(max(dp))


if __name__ == '__main__':
    main()

Solution (Python):

def main():
    import numpy as np

    N = int(input())
    happiness = [list(map(int, input().split())) for _ in range(N)]

    dp = np.zeros((N, 3), dtype=np.int64)
    dp[0] = happiness[0]
    for i in range(1, N):
        for a, yesterday in enumerate(dp[i - 1]):
            for b, today in enumerate(happiness[i]):
                if a == b:
                    continue
                dp[i][b] = max(dp[i][b], yesterday + today)
    print(max(dp[-1]))


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin 

def main():

	n = int(input())

	h_vals = []

	for lines in range(n):
		h = list(map(int, input().split()))
		h_vals.append(h)

	L = [ [0 for _ in range(n + 1)] for _ in range(3) ]


	for cur_day in range(1, n + 1):
		for val in range(3):
			cur_max = 0
			other_vals = [0, 1, 2]
			other_vals.remove(val)
			for other_val in other_vals:
				cur_max = max(L[other_val][cur_day - 1] + h_vals[cur_day - 1][other_val], cur_max)
			L[val][cur_day] = cur_max

	print(max(L[0][n], L[1][n], L[2][n]))









if __name__ == '__main__':
	main()

Solution (Python):
n = int(input())

vac = []
firstDay = list(map(int, input().split()))

for _ in range(n-1):
    newTotal = [0,0,0]
    
    secondDay = list(map(int, input().split()))
    for j, second in enumerate(secondDay):
        temp = 0
        for i, first in enumerate(firstDay):
            if i != j:
                temp = max(temp, first + second)
                
        newTotal[j] = temp   
                    
    firstDay = newTotal
    
print(max(firstDay))

Solution (Python):
n = int(input())

vac = []
firstDay = list(map(int, input().split()))

for _ in range(n-1):
    newTotal = [0,0,0]
    
    secondDay = list(map(int, input().split()))
    for j, second in enumerate(secondDay):
        temp = 0
        for i, first in enumerate(firstDay):
            if i != j:
                temp = max(temp, first + second)
                
        newTotal[j] = temp   
                    
    firstDay = newTotal
    
print(max(firstDay))

Solution (Python):













T=int(input())
A=[]
for x in range(T):
    l=[int(i) for i in input().split()]
    A.append(l)
A.append([0,0,0])

for i in range(T-1,-1,-1):
    for j in range(3):
        temp=0
        for k in range(3):
            if j!=k:
                temp=max(temp,A[i][j]+A[i+1][k])

        A[i][j]=max(A[i][j],temp)
    
    

print(max(A[0]))

Solution (Python):

n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]
dp = [[0, 0, 0] for _ in range(n+1)]
for i in range(n):
    dp[i+1][0] = abc[i][0] + max(dp[i][1], dp[i][2])
    dp[i+1][1] = abc[i][1] + max(dp[i][0], dp[i][2])
    dp[i+1][2] = abc[i][2] + max(dp[i][0], dp[i][1])
print(max(dp[n][0], max(dp[n][1], dp[n][2])))

Solution (Python):
N = int(input())
act = [list(map(int,input().split())) for _ in range(N)]
dp = [[0]*3 for _ in range(N+1)]

for i in range(N):
  dp[i+1][0] = max(dp[i][1], dp[i][2]) + act[i][0]
  dp[i+1][1] = max(dp[i][0], dp[i][2]) + act[i][1]
  dp[i+1][2] = max(dp[i][0], dp[i][1]) + act[i][2]
  
print(max(dp[N]))

Solution (Python):
n= int(input())
x=[]
for i in  range(n):
    x.append([int(x ) for  x in input().split()])

dp = [[x[0][0],x[0][1],x[0][2]] for i in range(n)]
for i in range(1,n):
    dp[i][0]=max(dp[i-1][1],dp[i-1][2])+x[i][0]
    dp[i][1]=max(dp[i-1][0],dp[i-1][2])+x[i][1]
    dp[i][2]=max(dp[i-1][1],dp[i-1][0])+x[i][2]
print(max(dp[n-1][0],dp[n-1][1],dp[n-1][2]))

Solution (Python):
n = int(input())
dp = [[0 for _ in range(3)] for _ in range(n + 1)]
ans = 0
for d in range(1, n + 1):
    abc = list(map(int, input().split()))
    for i in range(3):
        for j in range(3):
            if i == j:
                continue
            dp[d][j] = max(dp[d][j], dp[d - 1][i] + abc[j])
            ans = max(ans, dp[d][j])
print(ans)

Solution (Python):
N = int(input())
vac = []
for i in range(N):
    vac.append(list(map(int, input().split())))

dp = [[0 for _ in range(3)] for _ in range(N+1)]   

for i in range(N):
    for j in range(3):
        for k in range(3):
            if(j == k):
                continue
            dp[i+1][k] = max(dp[i+1][k], dp[i][j]+vac[i][k])
print(max(dp[-1]))

Solution (Python):
n = int(input())
abc = [tuple(map(int,input().split())) for i in range(n)]

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


for i in range(n):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][k] = max(dp[i+1][k],dp[i][j]+abc[i][k])

print(max(dp[-1]))

Solution (Python):
n=int(input())
a=[]
b=[]
c=[]

for _ in range(n):
	tmp=list(map(int,input().split()))
	a.append(tmp[0])
	b.append(tmp[1])
	c.append(tmp[2])
dp=[[0 for j in range(n)]for i in range(3)]
dp[0][0]=a[0]
dp[1][0]=b[0]
dp[2][0]=c[0]
for i in range(1,n):
	dp[0][i]=a[i]+max(dp[1][i-1],dp[2][i-1])
	dp[1][i]=b[i]+max(dp[2][i-1],dp[0][i-1])
	dp[2][i]=c[i]+max(dp[0][i-1],dp[1][i-1])
print(max(dp[0][n-1],dp[1][n-1],dp[2][n-1]))

Solution (Python):
def edu_dp_c_vacation():
    n = int(input())
    v = []
    for _ in range(n):
        v.append(list(map(int, input().split())))
    dp = [[0]*3 for _ in range(n)]
    dp[0] = v[0].copy()
    for i in range(1, n):
        for j in range(3):
            for k in range(3):
                if j == k: continue
                dp[i][j] = max(dp[i][j], dp[i-1][k]+v[i][j])
    print(max(dp[n-1]))
edu_dp_c_vacation()

Solution (Python):
n=int(input()) 
dp1,dp2,dp3=[0]*n,[0]*n,[0]*n
f=[]
for i in range(n):
	f.append([int(x) for x in input().split()])  
dp1[0]=f[0][0] 
dp2[0]=f[0][1] 
dp3[0]=f[0][2] 
for i in range(1,n):
	dp1[i]=f[i][0]+max(dp2[i-1],dp3[i-1]) 
	dp2[i]=f[i][1]+max(dp1[i-1],dp3[i-1])
	dp3[i]=f[i][2]+max(dp2[i-1],dp1[i-1])
print(max(dp1[-1],dp2[-1],dp3[-1]))

Solution (Python):
N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]
dpa = [abc[0][0]] + [0] * N
dpb = [abc[0][1]] + [0] * N
dpc = [abc[0][2]] + [0] * N
for i in range(1, N):
    dpa[i] = max(dpb[i-1], dpc[i-1]) + abc[i][0]
    dpb[i] = max(dpa[i-1], dpc[i-1]) + abc[i][1]
    dpc[i] = max(dpa[i-1], dpb[i-1]) + abc[i][2]

print(max(dpa[N-1], dpb[N-1], dpc[N-1]))

Solution (Python):
N=int(input())
INF=10**10
dp=[[-1]*3 for i in range(N)]
for i in range(N):
  abc=list(map(int,input().split()))
  if i==0:
    dp[0][0]=abc[0]
    dp[0][1]=abc[1]
    dp[0][2]=abc[2]
    continue
  for j in range(3):
    for k in range(3):
      if j==k:continue
      dp[i][j]=max(dp[i][j],dp[i-1][k]+abc[j])
print(max(dp[-1]))

Solution (Python):

n = int(input())
dp = [[0]*3]*(n)
an = list(map(int,input().split()))
dp[0] = an
for i in range(1,n):
    
    a,b,c = list(map(int, input().split()))
    
    
    a_m = max(dp[i-1][1]+a, dp[i-1][2]+a)
    b_m = max(dp[i-1][0]+b, dp[i-1][2]+b)
    c_m = max(dp[i-1][0]+c, dp[i-1][1]+c) 
    dp[i] = [a_m,b_m,c_m]

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

Solution (Python):

n = int(input())
summmer = [""]*n
for i in range(n):
    summmer[i] = list(map(int,input().split()))
happy = [0]*(n+1)
for i in range(n+1):
    happy[i] = [0]*3
yesterday = -1
for i in range(1,n+1):
    happy[i][0] = max(happy[i-1][1] + summmer[i-1][0],happy[i-1][2] + summmer[i-1][0]) 
    happy[i][1] = max(happy[i-1][0] + summmer[i-1][1],happy[i-1][2] + summmer[i-1][1]) 
    happy[i][2] = max(happy[i-1][0] + summmer[i-1][2],happy[i-1][1] + summmer[i-1][2]) 

print(max(happy[-1]))

Solution (Python):
import math
n=int(input())
dp=[[0]*3 for i in range(n+1)]
s=[]
for i in range(n):
    arr=list(map(int,input().split()))
    s.append(arr)

for i in range(n):
    for j in range(3):
        for k in range(3):
            if j==k:
                continue
            dp[i+1][j]=max(dp[i][k]+s[i][j],dp[i+1][j])
print(max(dp[n]))

Solution (Python):

import numpy as np
import warnings
warnings.filterwarnings('ignore')

N = int(input())
h = np.array([list(map(int, input().split())) for _ in range(N)])

h = h.reshape(N, 3)

dp = np.array([[0] * h.shape[1]] * h.shape[0])
dp[0, :] = h[0, :]
for i in range(1, N):
    dp[i, 0] = max(dp[i-1, 1], dp[i-1, 2])+h[i, 0]
    dp[i, 1] = max(dp[i-1, 0], dp[i-1, 2])+h[i, 1]
    dp[i, 2] = max(dp[i-1, 0], dp[i-1, 1])+h[i, 2]

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

Solution (Python):
n = int(input())
dp = [[-1]*3 for _ in range(n+1)]

for i in range(3):
    dp[0][i] = 0

for i in range(n):
    a, b, c = map(int, input().split())
    dp[i+1][0] = max(dp[i][1]+a, dp[i][2]+a)
    dp[i+1][1] = max(dp[i][0]+b, dp[i][2]+b)
    dp[i+1][2] = max(dp[i][0]+c, dp[i][1]+c)

print(max(dp[n]))

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
N=int(input())
ABC=[]
for _ in range(N):
    ABC.append(list(map(int,input().split())))
from functools import lru_cache
@lru_cache(maxsize=None)
def dynam(n):
    if n>1:
        a=max(dynam(n-1)[1]+ABC[n-1][0],
              dynam(n-1)[2]+ABC[n-1][0])
        b=max(dynam(n-1)[0]+ABC[n-1][1],
              dynam(n-1)[2]+ABC[n-1][1])
        c=max(dynam(n-1)[0]+ABC[n-1][2],
              dynam(n-1)[1]+ABC[n-1][2])
        return (a,b,c)
    return tuple(ABC[0])
print(max(dynam(N)))

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
N=int(input())
ABC=[]
for _ in range(N):
    ABC.append(list(map(int,input().split())))
from functools import lru_cache
@lru_cache(maxsize=None)
def dynam(n):
    if n>1:
        a=max(dynam(n-1)[1]+ABC[n-1][0],
              dynam(n-1)[2]+ABC[n-1][0])
        b=max(dynam(n-1)[0]+ABC[n-1][1],
              dynam(n-1)[2]+ABC[n-1][1])
        c=max(dynam(n-1)[0]+ABC[n-1][2],
              dynam(n-1)[1]+ABC[n-1][2])
        return (a,b,c)
    return tuple(ABC[0])
print(max(dynam(N)))

Solution (Python):
n=int(input())
a,b,c=[],[],[]
for _ in range(n):
  A,B,C=map(int,input().split())
  a.append(A)
  b.append(B)
  c.append(C)

dp=[[[0] for _ in range(3)] for _ in range(n)]
dp[0][0]=a[0]
dp[0][1]=b[0]
dp[0][2]=c[0]

for i in range(1,n):
  dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][2]+a[i])
  
  dp[i][1]=max(dp[i-1][0]+b[i],dp[i-1][2]+b[i])
  
  dp[i][2]=max(dp[i-1][0]+c[i],dp[i-1][1]+c[i])
  
  

print(max(dp[-1][0],dp[-1][1],dp[-1][2]))

Solution (Python):

n = int(input())
x = [-1]*n
for i in range(n):
    x[i] = list(map(int, input().split()))

ans = [[0]*3 for i in range(n)]
ans[0] = x[0]

for k in range(1,n):
    for j in range(3):
        ans[k][j] = max(ans[k-1][(j+1)%3], ans[k-1][(j+2)%3]) + x[k][j]

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

Solution (Python):
N = int(input())
happy = [[0, 0, 0]]
for _ in range(N):
    happy.append(list(map(int, input().split())))

dp = [[0, 0, 0] for _ in range(N+1)]

for i in range(1,N+1):
    for today in range(3):
        for yesterday in range(3):
            if today == yesterday: continue

            dp[i][today] = max(dp[i][today], dp[i-1][yesterday] + happy[i][today])

print(max(dp[N][0], dp[N][1], dp[N][2]))

Solution (Python):
def main():
    N = int(input())
    v = [list(map(int,input().split())) for _ in range(N)]
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + v[i][0]
        dp[i+1][1] = max(dp[i][0],dp[i][2]) + v[i][1]
        dp[i+1][2] = max(dp[i][0],dp[i][1]) + v[i][2]
    print(max(dp[N][i] for i in range(3)))
    
main()

Solution (Python):
def main():
    N = int(input())
    v = [list(map(int,input().split())) for _ in range(N)]

    dp = [[0]*3 for _ in range(N+1)]

    for i in range(N):
        for j in range(3):
            for k in range(3):
                if j==k:continue
                dp[i+1][k] = max(dp[i+1][k],dp[i][j]+v[i][k])
    print(max(dp[N][i] for i in range(3)))
main()

Solution (Python):
N = int(input())
v = [list(map(int,input().split())) for _ in range(N)]

dp = [[0]*3 for _ in range(N+1)]

for i in range(N):
    for j in range(3):
        for k in range(3):
            if j==k:continue
            dp[i+1][k] = max(dp[i+1][k],dp[i][j]+v[i][k])
            
print(max(dp[N][i] for i in range(3)))

Solution (Python):
def solve():
    N = int(input())
    dp = [[0] * 3 for i in range(N + 1)]
    for i in range(N):
        A = list(map(int, input().split()))
        for j in range(3):
            for k in range(3):
                if j != k:
                    dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + A[k])
    return max(dp[N])

print(solve())

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N = int(input())
A = []
for _ in range(N):
    a,b,c = map(int,input().split())
    A.append((a,b,c))
    

INF = 10**10



dp = [[0]*3 for _ in range(100010)]


for i in range(100010):
    for j in range(3):
        dp[i][j] = 0

def rec(v):
    
    for w in range(3):
        
        if dp[v][w] > 0:
            return dp[v]
        
        if v == 0:
            dp[v][w] = 0
            return dp[v]
        
        res = 0
        for k in range(3):
            
            if w == k:
                continue
            res = max(res, rec(v-1)[k] + A[v-1][w])
            
            dp[v][w] = res
    return dp[v]
rec(N)
ans = max(dp[N])
print(ans)

Solution (Python):

N = int(input())
A = []
for _ in range(N):
    a,b,c = map(int,input().split())
    A.append((a,b,c))
    

INF = 10**10



dp = [[0]*3 for _ in range(100010)]


for i in range(100010):
    for j in range(3):
        dp[i][j] = -INF
        

dp[0][0],dp[0][1],dp[0][2] = 0,0,0
        

for v in range(1,N+1):
    
    for w in range(3):
        
        for k in range(3):
            
            if w == k:
                continue
            
            dp[v][w] = max(dp[v][w], dp[v-1][k] + A[v-1][w])


ans = max(dp[N])            
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
N = int(input())
A = []
for _ in range(N):
    a,b,c = map(int,input().split())
    A.append((a,b,c))


INF = 10**10


dp = [[0]*3 for _ in range(100010)]


for i in range(5):
    for j in range(3):
        dp[i][j] = 0

def rec(v):
    
    for w in range(3):
        
        if dp[v][w] > 0:
       
            return dp[v]
        if v == 0:
            dp[v][w] = 0
         
            return dp[v]
        res = 0
        
        for k in range(3):
            if w == k:
               
                continue
            res = max(res,rec(v-1)[k] + A[v-1][w]) 
            dp[v][w] = res 
            
    return dp[v]

rec(N)
ans = max(dp[N])
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**5+10)

input = sys.stdin.readline

vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]


dp = [[0 for i in range(3)] for j in range(vacation+1)]

def chmax(a, b):
    if a > b:
        return a
    else:
        return b

def rec(i):
    
    for j in range(3):
        if dp[i][j] > 0:
            break
        
        
        if i == 0:
            dp[i][j] = 0
            break
        
        
        res = 0
        for k in range(3):
            if j == k:
                continue
            res = chmax(res, rec(i-1)[k] + lst_happiness[i-1][k])
            
            dp[i][j] = res
    
    return dp[i]
ans = rec(vacation)
ans = max(ans)
print(ans)

Solution (Python):
import sys

input = sys.stdin.readline

vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]


dp = [[0 for i in range(3)] for j in range(vacation+1)]
def chmax(a, b):
    if a > b:
        return a
    else:
        return b








for i in range(vacation):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][k] = chmax(dp[i+1][k], dp[i][j] + lst_happiness[i][k])
ans = 0
for i in range(3):
    ans = chmax(ans, dp[vacation][i])
print(ans)

Solution (Python):
N=int(input())

A=[[0]*3 for i in range(N+1)]
for i in range(N):
  a=list(map(int,input().split()))
  A[i]=a


dp=[[-float('inf')] * 3 for i in range(N+1)]



dp[0]=A[0] 


for i in range(N):
  for j in range(3): 
    for k in range(3): 
      if j != k: 
        if dp[i+1][k] < dp[i][j] + A[i+1][k]:
          dp[i+1][k] = dp[i][j] + A[i+1][k]
        

ans=max(dp[N-1])
print(ans)

Solution (Python):

"""
n, k = [int(i) for i in input().split(' ')]

arr = [int(i) for i in input().split(' ')]

dp = [10**10]*n

k += 1
dp[0] = 0

for i in range(0, n):
    for j in range(1, k):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(arr[i+j]-arr[i]))

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

n = int(input())

a = [int(i) for i in input().split(' ')]

for i in range(1, n):
    new_a = [int(i) for i in input().split(' ')]
    new_a[0] = max(new_a[0]+a[1], new_a[0]+a[2])
    new_a[1] = max(new_a[1]+a[0], new_a[1]+a[2])
    new_a[2] = max(new_a[2]+a[1], new_a[2]+a[0])
    a, new_a = new_a, a

print(max(a))

Solution (Python):

N = int(input())
A = []
for _ in range(N):
    a,b,c = map(int,input().split())
    A.append((a,b,c))
    

INF = 10**10



dp = [[0]*3 for _ in range(100010)]


for i in range(100010):
    for j in range(3):
        dp[i][j] = -INF
        

dp[0][0],dp[0][1],dp[0][2] = 0,0,0
        

for v in range(1,N+1):
    
    for w in range(3):
        
        for k in range(3):
            
            if w == k:
                continue
            
            dp[v][k] = max(dp[v][k], dp[v-1][w] + A[v-1][k])


ans = max(dp[N])            
print(ans)

Solution (Python):
N = int(input())
a = [0] * N
b = [0] * N
c = [0] * N

for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())




S = [[0 for j in range(3)] for i in range(N)]
S[0][0] = a[0]
S[0][1] = b[0]
S[0][2] = c[0]

for i in range(1, N):
    S[i][0] = max(S[i - 1][1], S[i - 1][2]) + a[i]
    S[i][1] = max(S[i - 1][0], S[i - 1][2]) + b[i]
    S[i][2] = max(S[i - 1][0], S[i - 1][1]) + c[i]


print(max(S[N - 1]))

Solution (Python):
n=int(input())
INF=float('inf')

H=[]
for _ in range(n):
  a,b,c=map(int,input().split())
  H.append([a,b,c])
  
dp=[[0 for i in range(3)] for j in range(n+1)]
for i in range(1,n+1):
  dp[i][0]=max(dp[i-1][1]+H[i-1][0],dp[i-1][2]+H[i-1][0])
  dp[i][1]=max(dp[i-1][2]+H[i-1][1],dp[i-1][0]+H[i-1][1])
  dp[i][2]=max(dp[i-1][0]+H[i-1][2],dp[i-1][1]+H[i-1][2])

print(max(dp[n][0],dp[n][1],dp[n][2]))

Solution (Python):
n=int(input())
p=[]
for _ in range(n):
    p.append(list(map(int,input().split())))
dp=[[0,0,0] for _ in range(n)]
dp[0][0]=p[0][0]
dp[0][1]=p[0][1]
dp[0][2]=p[0][2]
for i in range(1,n):
    dp[i][0]=p[i][0]+max(dp[i-1][1],dp[i-1][2])
    dp[i][1]=p[i][1]+max(dp[i-1][0],dp[i-1][2])
    dp[i][2]=p[i][2]+max(dp[i-1][0],dp[i-1][1])
    
print(max(dp[-1]))

Solution (Python):
N = int(input())
a,b,c = [],[],[]
for n in range(N):
  a_,b_,c_ = map(int, input().split())
  a.append(a_)
  b.append(b_)
  c.append(c_)
do_a = [a[0]] 
do_b = [b[0]] 
do_c = [c[0]]

for day in range(1,N):
  do_a.append(a[day] + max(do_b[day-1], do_c[day-1]))
  do_b.append(b[day] + max(do_a[day-1], do_c[day-1]))
  do_c.append(c[day] + max(do_a[day-1], do_b[day-1]))
print(max(do_a[N-1],do_b[N-1], do_c[N-1]))

Solution (Python):
from itertools import permutations as P

N = int(input())
V = [tuple(map(int, input().split())) for _ in range(N)]

dp = [[0]*3 for _ in range(N+1)]

l = tuple(P(range(3), 2))

for i in range(N):
	for j in range(6):
		a, b = l[j]

		dp[i+1][b] = max(dp[i+1][b], dp[i][a] + V[i][b])


print(max(dp[-1]))

Solution (Python):
N = int(input())
dp = [[0 for _ in range(3)] for _ in range(N + 1)]
a, b, c = map(int, input().split())
dp[1][0] = a
dp[1][1] = b
dp[1][2] = c
for i in range(2, N + 1):
    a, b, c = map(int, input().split())
    dp[i][0] = max(dp[i - 1][1] + a, dp[i - 1][2] + a)
    dp[i][1] = max(dp[i - 1][0] + b, dp[i - 1][2] + b)
    dp[i][2] = max(dp[i - 1][0] + c, dp[i - 1][1] + c)

print(max(dp[N]))

Solution (Python):
n =int(input())
l = [list(map(int,input().split())) for i in range(n)]

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

for i in range(n):
  if i==0:
    dp[0]=l[0]
  else:
    dp[i][0]=max(dp[i][0],dp[i-1][1]+l[i][0],dp[i-1][2]+l[i][0])
    dp[i][1]=max(dp[i][1],dp[i-1][0]+l[i][1],dp[i-1][2]+l[i][1])
    dp[i][2]=max(dp[i][2],dp[i-1][0]+l[i][2],dp[i-1][1]+l[i][2])
print(max(dp[n-1]))

Solution (Python):
from copy import deepcopy


def solve(N, abc):
    dp = [[0, 0, 0] for i in range(N+1)]

    for i in range(1, N+1):
        for j in range(3):
            tmp = []
            for d in dp[i-1]:
                tmp.append(d)
            tmp.pop(j)
            dp[i][j] = max(tmp) + abc[i-1][j]

    return(max(dp[N]))


if __name__ == "__main__":
    N = int(input())
    abc = [list(map(int, input().split())) for _ in range(N)]
    print(solve(N, abc))

Solution (Python):
from copy import deepcopy


def solve(N, abc):
    dp = [[0, 0, 0] for i in range(N+1)]

    for i in range(1, N+1):
        for j in range(3):
            tmp = deepcopy(dp[i-1])
            tmp.pop(j)
            dp[i][j] = max(tmp) + abc[i-1][j]

    return(max(dp[N]))


if __name__ == "__main__":
    N = int(input())
    abc = [list(map(int, input().split())) for _ in range(N)]
    print(solve(N, abc))

Solution (Python):
from copy import deepcopy


def solve(N, abc):
    dp = [[0, 0, 0] for i in range(N+1)]

    for i in range(1, N+1):
        for j in range(3):
            tmp = deepcopy(dp[i-1])
            tmp.pop(j)
            dp[i][j] = max(tmp) + abc[i-1][j]

    return(max(dp[N]))


if __name__ == "__main__":
    N = int(input())
    abc = [list(map(int, input().split())) for _ in range(N)]
    print(solve(N, abc))

Solution (Python):

n = int(input())
dp1 = [0] * n
dp2 = [0] * n
dp3 = [0] * n

a, b, c = map(int,input().split())
dp1[0] = a
dp2[0] = b
dp3[0] = c
for i in range(1,n):
    a, b, c = map(int,input().split())
    dp1[i] = max(dp2[i-1]+a, dp3[i-1]+a)
    dp2[i] = max(dp1[i-1]+b, dp3[i-1]+b)
    dp3[i] = max(dp2[i-1]+c, dp1[i-1]+c)
print(max(dp1[n-1], dp2[n-1], dp3[n-1]))

Solution (Python):
n=int(input())
H=[list(map(int,input().split())) for i in range(n)]
dp=[[0 for i in range(3)] for i in range(n)]
for i in range(3):
    dp[0][i]=H[0][i]
for i in range(n-1):
    for j in range(3):
        if j==0:
            dp[i+1][0]=max(dp[i][1]+H[i+1][0],dp[i][2]+H[i+1][0])
        if j==1:
            dp[i+1][1]=max(dp[i][0]+H[i+1][1],dp[i][2]+H[i+1][1])
        if j==2:
            dp[i+1][2]=max(dp[i][0]+H[i+1][2],dp[i][1]+H[i+1][2])
print(max(dp[n-1][0],dp[n-1][1],dp[n-1][2]))

Solution (Python):
N=int(input())
l=[[0,0,0]]+[list(map(int,input().split())) for _ in range(N)]

sum=[[0]*3 for _ in range(N+1)]
for i in range(1,N+1):
    sum[i][0]=max(sum[i-1][1],sum[i-1][2])+l[i][0]
    sum[i][1]=max(sum[i-1][0],sum[i-1][2])+l[i][1]
    sum[i][2]=max(sum[i-1][0],sum[i-1][1])+l[i][2]
ans=max(sum[N])
print(ans)

Solution (Python):
from sys import stdin
input=lambda : stdin.readline().strip()
from math import ceil,sqrt,factorial,gcd
from collections import deque
n=int(input())
prev=0
l=[]
for i in range(n):
	l.append(list(map(int,input().split())))
z=[[0,0,0] for i in range(n)]
z[0]=l[0]
for i in range(1,n):
	z[i][0]=l[i][0]+max(z[i-1][1],z[i-1][2])
	z[i][2]=l[i][2]+max(z[i-1][1],z[i-1][0])
	z[i][1]=l[i][1]+max(z[i-1][0],z[i-1][2])
print(max(z[-1]))

Solution (Python):
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]

dp = [[0]*3 for _ in range(n+1)]

for i in range(n):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][j] = max(abc[i][j]+dp[i][k], dp[i+1][j])
            dp[i+1][k] = max(abc[i][k]+dp[i][j], dp[i+1][k])

print(max(dp[-1]))

Solution (Python):
def maxExept(lis):
    data = [0,0,0]
    data[0] = max(lis[1],lis[2])
    data[1] = max(lis[0],lis[2])
    data[2] = max(lis[0],lis[1])
    return data
k = int(input())
grid = []
for i in range(k):
  x = list(map(int,input().split(' ')))
  grid.append(x)
for i in range(len(grid)-2,-1,-1):
    x,y,z = maxExept(grid[i+1])
    grid[i][0] +=x
    grid[i][1] +=y
    grid[i][2] +=z
print(max(grid[0]))

Solution (Python):
n=int(input())
A=[]
B=[]
C=[]
for i in range(n):
    
    a,b,c = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    
dp = [[0,0,0] for i in range(n)]

dp[0] =[A[0],B[0],C[0]]

for i in range(1,n):
    
    a = max(dp[i-1][1], dp[i-1][2]) + A[i]
    b = max(dp[i-1][2], dp[i-1][0]) + B[i]
    c = max(dp[i-1][0], dp[i-1][1]) + C[i]
    
    dp[i] = [a,b,c]
    
print(max(dp[-1]))

Solution (Python):
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]

a, b, c = [0], [0], [0]
for i in abc:
  aa = i[0] + max(b[-1], c[-1])
  bb = i[1] + max(c[-1], a[-1])
  cc = i[2] + max(a[-1], b[-1])
  a.append(aa)
  b.append(bb)
  c.append(cc)
print(max(a[-1], b[-1], c[-1]))

Solution (Python):
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]

aabbcc = [[0], [0], [0]]
tmp = [0]*3
for i in abc:
  for j in range(3):
    tmp[j] = i[j] + max(aabbcc[(j+1)%3][-1], aabbcc[(j+2)%3][-1])
  for j in range(3):
    aabbcc[j].append(tmp[j])
print(max([i[-1] for i in aabbcc]))

Solution (Python):
N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]
 
A = [0]
B = [0]
C = [0]
for i in range(N):
    a = abc[i][0] + max(B[-1], C[-1])
    b = abc[i][1] + max(A[-1], C[-1])
    c = abc[i][2] + max(A[-1], B[-1])
    A += [a]
    B += [b]
    C += [c]
print(max(A[-1], B[-1], C[-1]))

Solution (Python):
N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]
 
A = [0]
B = [0]
C = [0]
for i in range(N):
    a = abc[i][0] + max(B[-1], C[-1])
    b = abc[i][1] + max(A[-1], C[-1])
    c = abc[i][2] + max(A[-1], B[-1])
    A += [a]
    B += [b]
    C += [c]
print(max(A[-1], B[-1], C[-1]))