Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import math
from collections import Counter
from functools import reduce
from operator import mul


def get_divisors(n):
    """
    n の約数をリストで返す
    :param int n:
    :return:
    """
    ret = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            if n // i != i:
                ret.append(n // i)
    return ret


def get_factors(n):
    """
    素因数分解
    :param int n:
    :type: list of int
    """
    ret = []
    i = 2
    while 2 <= i <= n:
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 1
    return ret


def comb(n, r):
    """
    組み合わせの数 nCr
    :param n:
    :param r:
    :return:
    """
    r = min(n - r, r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))


n, m = map(int, input().split())
MOD = 10 ** 9 + 7

# divs = sorted(get_divisors(m))
# # dp[d]: 累積積が d となる数列の数
# dp = {d: 1 for d in divs}
# for _ in range(n - 1):
#     for i in reversed(range(len(divs))):
#         div = divs[i]
#         dp[div] = sum([dp[d] for d in divs if div % d == 0]) % MOD
#     print(dp)
# print(dp)
# おそい


factors = get_factors(m)
counts = Counter(factors)
# k**v を全部かけあわせたやつが m に一致する
# print(functools.reduce(operator.mul, [k ** v for k, v in counts.items()]))

# v 個の k を n 個の数に配分する組み合わせの数
# → v + (n-1) 個のスペースへの v の置き方の組み合わせの数
ans = 1
for k, v in counts.items():
    ans *= comb(v + (n - 1), v)
    ans %= MOD
print(ans)


### FIXED CODE ###

import math
from collections import Counter
from functools import reduce
from operator import mul


def get_factors(n):
    """
    素因数分解
    :param int n:
    :type: list of int
    """
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


def comb(n, r):
    """
    組み合わせの数 nCr
    :param n:
    :param r:
    :return:
    """
    r = min(n - r, r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))


n, m = map(int, input().split())
MOD = 10 ** 9 + 7

# divs = sorted(get_divisors(m))
# # dp[d]: 累積積が d となる数列の数
# dp = {d: 1 for d in divs}
# for _ in range(n - 1):
#     for i in reversed(range(len(divs))):
#         div = divs[i]
#         dp[div] = sum([dp[d] for d in divs if div % d == 0]) % MOD
#     print(dp)
# print(dp)
# おそい


factors = get_factors(m)
counts = Counter(factors)
# k**v を全部かけあわせたやつが m に一致する
# print(functools.reduce(operator.mul, [k ** v for k, v in counts.items()]))

# v 個の k を n 個の数に配分する組み合わせの数
# → v + (n-1) 個のスペースへの v の置き方の組み合わせの数
ans = 1
for k, v in counts.items():
    ans *= comb(v + (n - 1), v)
    ans %= MOD
print(ans)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
N = int(input())
a = list(map(int, input().split()))
minimum = float('inf')
for tmp in range(1,N):
    b = abs(sum(a[0:tmp])-sum(a[tmp:len(a)]))
    minimum = min(minimum, b)
print(minimum)

### FIXED CODE ###

# -*- coding:utf-8 -*-
N = int(input())
a = list(map(int, input().split()))
b = sum(a)
c = 0
minimum = float('inf')
for tmp in range(0,N-1):
    c += a[tmp]    
    d = abs(c-(b-c))
    minimum = min(minimum, d)
print(minimum)
### BUGGY CODE ###

n=int(input())
a=[]
for _ in range(n):
    a.append(int(input()))

count=0
for a_ele in set(a):
    if a.count(a_ele)%2==1:
        count+=1

print(count)

### FIXED CODE ###

n=int(input())
a={}
for _ in range(n):
    num=int(input())
    if num not in a:
        a[num]=1
    else:
        a[num]+=1
all_count=0
for _, count in a.items():
    if count%2==1:
        all_count+=1
print(all_count)
### BUGGY CODE ###

def gcd(a, b):
    if b > a:
        gcd(b, a)
    while b:
	    a, b = b, a % b
    return a

n,m = map(int, input().split())
s = input()
t = input()

l = n * m // gcd(n, m)
a = l // n
b = l // m
#print(a, b)
#a(i-1) = b(j-i) -> ai = bj + (a-b)
res = False
clear_all = True
for i in range(1,n+1):
    for j in range(1,m+1):
        if a * i - b * j == a - b:
            if not s[i-1] == t[j-1]:
                clear_all = False
if clear_all:
    res = True
if res:
    print(l)
else:
    print(-1)
        

### FIXED CODE ###

def gcd(a, b):
    if b > a:
        gcd(b, a)
    while b:
	    a, b = b, a % b
    return a

n,m = map(int, input().split())
s = input()
t = input()

l = n * m // gcd(n, m)
a = l // n
b = l // m
#print(a, b)
#a(i-1) = b(j-i) -> ai = bj + (a-b)
res = False
clear_all = True
for i in range(1,n+1):
    if (a*i - (a-b)) % b == 0:
        j = (a * i - (a-b)) // b
        if not s[i-1] == t[j-1]:
            clear_all = False
if clear_all:
    res = True
if res:
    print(l)
else:
    print(-1)
### BUGGY CODE ###

n,k=map(int,input().split())
digit=1
num=k
while n>=k:
  num *= k
  digit += 1

print(digit)
  

### FIXED CODE ###

import math
n,k=map(int,input().split())
print(int(math.log(n,k)) + 1)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
B = [0] + LI()

A = [0,B[1]]
for i in range(1,N):
    if B[i] != B[i+1]:
        A.append(B[i+1])

N = len(A)-1

from functools import lru_cache

@lru_cache(maxsize=None)
def dfs(n,money):
    if n == N+1:
        return money
    else:
        res = money
        for i in range(n,N):  # 購入
            for j in range(i+1,N+1):  # 売却
                if A[i] == min(A[i:j+1]) and A[j] == max(A[i:j+1]) and A[i] < A[j]:
                    res = max(res,dfs(j+1,money+(A[j]-A[i])*(money//A[i])))
        return res

print(dfs(1,1000))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
B = [0] + LI()

A = [0,B[1]]
for i in range(1,N):
    if B[i] != B[i+1]:
        A.append(B[i+1])

N = len(A)-1

MAX = [0,1000] + [0]*N

from functools import lru_cache

@lru_cache(maxsize=None)
def dfs(n,money):
    if n == N+1:
        return money
    else:
        res = money
        for i in range(n,N):  # 購入
            for j in range(i+1,N+1):  # 売却
                if A[i] == min(A[i:j+1]) and A[j] == max(A[i:j+1]) and A[i] < A[j]:
                    if money+(A[j]-A[i])*(money//A[i]) > MAX[j+1]:
                        res = max(res,dfs(j+1,money+(A[j]-A[i])*(money//A[i])))
                        MAX[j+1] = money+(A[j]-A[i])*(money//A[i])
        return res

print(dfs(1,1000))
### BUGGY CODE ###

import math
A, B, N = map(int, input().split())

d = 0
ans = 0
for i in range(1, N+1):
    d = math.floor((A*i)/B) - A*math.floor(i/B)
    if ans <= d:
        ans = d
    else:
        print(ans)
        exit()
        
print(ans)

### FIXED CODE ###

import math

A, B, N = map(int, input().split())
print(math.floor((A * min(B-1, N)) / B) - A * math.floor(min(B-1, N) / B))
### BUGGY CODE ###

from collections import deque

h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))

q = deque()
d = [[-1]*w for x in range(h)]

for i in range(h):
    for j in range(w):
        if m[i][j] == "#":
            q.append([i,j])
            d[i][j] = 0

aa = 0
while q:
    v = q.popleft()
    count = 0
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0] + i[0]
        nx = v[1] + i[1]
        if (0<=ny<h and 0<=nx<w and m[ny][nx] == "."):
            m[ny][nx] = "#"
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1
            aa = max(aa,d[ny][nx])

######
print(aa)

### FIXED CODE ###

from collections import deque

h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))

q = deque()
d = [[-1]*w for x in range(h)]

for i in range(h):
    for j in range(w):
        if m[i][j] == "#":
            q.append([i,j])
            d[i][j] = 0

aa = 0
while q:
    v = q.popleft()
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0] + i[0]
        nx = v[1] + i[1]
        if (0<=ny<h and 0<=nx<w and m[ny][nx] == "."):
            m[ny][nx] = "#"
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1
            aa = max(aa,d[ny][nx])

######
print(aa)
### BUGGY CODE ###

n=int(input())
A=[]
for i in range(n):
  A.append(input())
  
PM=[[0,0] for i in range(n)]
for i in range(n):
    now=0
    mini=0
    for j in A[i]:
        if j=="(": now+=1 
        else:
            now-=1 ; mini=min(mini,now)
    PM[i]=[mini,now]

if sum([PM[i][1] for i in range(n)]  )!=0 : 
    print("No")
    exit()

MINI=0
NOW=0
PMf=[PM[i] for i in range(n) if PM[i][1]>=0]
PMf.sort()
for i in range(len(PMf)):
    MINI=min(MINI , NOW+PMf[-i-1][0] )
    NOW+=PMf[-i-1][1]
    if MINI<0 : print("No") ; exit()

PMs=[PM[i] for i in range(n) if PM[i][1]<0]
PMs=sorted(PMs , key=lambda x : x[1]-x[0])
for i in range(len(PMs)):
    MINI=min(MINI , NOW+PMs[-i-1][0] )
    NOW+=PMs[-i-1][1]
    if MINI<0 : print("No") ; exit()

print("Yes")


### FIXED CODE ###

import sys
input=lambda: sys.stdin.readline().strip()


n=int(input())
A=[]
#
PM=[[0,0] for i in range(n)]
for i in range(n):
    now=0
    mini=0
    for j in input():
        if j=="(": now+=1 
        else:
            now-=1 ; mini=min(mini,now)
    PM[i]=[mini,now]

if sum( [PM[i][1] for i in range(n)]  )!=0 : 
    print("No")
    exit()

MINI=0
NOW=0
PMf=[PM[i] for i in range(n) if PM[i][1]>=0]
PMf.sort()
for i in range(len(PMf)):
    MINI=min(MINI , NOW+PMf[-i-1][0] )
    NOW+=PMf[-i-1][1]
    if MINI<0 : print("No") ; exit()

PMs=[PM[i] for i in range(n) if PM[i][1]<0]
PMs=sorted(PMs , key=lambda x : x[1]-x[0])
for i in range(len(PMs)):
    MINI=min(MINI , NOW+PMs[-i-1][0] )
    NOW+=PMs[-i-1][1]
    if MINI<0 : print("No") ; exit()

print("Yes")
### BUGGY CODE ###

import numpy as np

n, x, y = map(int,input().split())
ans = np.zeros(n-1, dtype=np.int)

for i in range(1,n):
    for j in range(i+1,n+1):
        if j <= x or y <= i:
            dist = j - i
        else:
            dist = j - i
            short = abs(x - i) + 1 + abs(y - j)
            if short < dist:
                dist = short
        ans[dist-1] = ans[dist-1] + 1

for k in ans:
    print(k)

### FIXED CODE ###

n, x, y = map(int,input().split())
ans = [0]*(n-1)

for i in range(1,n):
    for j in range(i+1,n+1):
        if j <= x or y <= i:
            dist = j - i
        else:
            dist = j - i
            short = abs(x - i) + 1 + abs(y - j)
            dist = min(dist, short)
        ans[dist-1] += 1

for k in ans:
    print(k)
### BUGGY CODE ###

k=int(input())
keta=2
unta=[[]]*10
unta[0]=["1","2","3","4","5","6","7","8","9"]
for _ in range(9):
	for i in range(len(unta[keta-2])):
		if unta[keta-2][i][len(unta[keta-2][i])-1]=="0":
			unta[keta-1].append(("").join(unta[keta-2][i])+"0")
			unta[keta-1].append(("").join(unta[keta-2][i])+"1")
		if unta[keta-2][i][len(unta[keta-2][i])-1]=="9":
			unta[keta-1].append(("").join(unta[keta-2][i])+"8")
			unta[keta-1].append(("").join(unta[keta-2][i])+"9")
		else:
			unta[keta-1].append(("").join(unta[keta-2][i])+str(int(unta[keta-2][i][len(unta[keta-2][i])-1])-1))
			unta[keta-1].append(("").join(unta[keta-2][i])+str(int(unta[keta-2][i][len(unta[keta-2][i])-1])))
			unta[keta-1].append(("").join(unta[keta-2][i])+str(int(unta[keta-2][i][len(unta[keta-2][i])-1])+1))
	keta += 1
unchi=[]
for i in range(10):
	unchi+=unta[i]
print(unchi[k-1])

### FIXED CODE ###

k=int(input())
unta=[[],[],[],[],[],[],[],[],[],[],[],[]]
unta[1]=["1","2","3","4","5","6","7","8","9"]
for keta in range(2,12):
	for i in range(len(unta[keta-1])):
		if unta[keta-1][i][keta-2]=="0":
			unta[keta].append(unta[keta-1][i]+"0")
			unta[keta].append(unta[keta-1][i]+"1")
		elif unta[keta-1][i][keta-2]=="9":
			unta[keta].append(unta[keta-1][i]+"8")
			unta[keta].append(unta[keta-1][i]+"9")
		else:
			unta[keta].append(unta[keta-1][i]+str(int(unta[keta-1][i][keta-2])-1))
			unta[keta].append(unta[keta-1][i]+unta[keta-1][i][keta-2])
			unta[keta].append(unta[keta-1][i]+str(int(unta[keta-1][i][keta-2])+1))
unchi=[]
for i in range(11):
	unchi+=unta[i]
print(unchi[k-1])
### BUGGY CODE ###

n,k = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()  #从小到大
F.sort(reverse=True)  #从大到小

def isOk(x):
    cost = 0
    for a, f in zip(A,F):
        eatable = x//f
        if eatable >= a:
            continue
        cost += a - eatable
        if cost > k:
          return False
    return True

left = -1
right = A[-1] * F[0]
while left+1 < right:
    # mid = int(left + (right-left)//2)
    mid = (left+right)//2
    if isOk(mid):
        right = mid
    else:
        left = mid
print(right)

### FIXED CODE ###

import numpy as np
i8 = np.int64
i4 = np.int32


def solve(A, F, K):
    min_ = 0
    max_ = 10 ** 12
    while min_ < max_:
        mid = (min_ + max_) // 2
        count = A - mid // F
        sum_ = count[count > 0].sum()
        if sum_ <= K:
            max_ = mid
        else:
            min_ = mid + 1
    return min_

def main():
    stdin = open('/dev/stdin', 'rb')
    pin = np.fromstring(stdin.read(), i8, sep=' ')
    N, K = pin[:2]
    A = pin[2: N + 2]
    F = pin[N + 2: 2 * N + 2]
    A = np.sort(A)[::-1]
    F.sort()
    ans = solve(A, F, K)
    print(ans)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
S = sorted([input() for i in range(N)])
T = sorted(list(set(S)))
count = [0] * len(T)
for i in range(len(T)):
        count[i] = len([j for j, k in enumerate(S) if k == T[i]])
count_index = [k for k, l in enumerate(count) if l == max(count)]
for m in count_index:
    print(T[m])

### FIXED CODE ###

from collections import Counter
n = int(input())
S = [input() for _ in range(n)]

poll = Counter(S)
max_c = max(list(poll.values()))
ans = [k for k in poll.keys() if poll[k] == max_c]
ans.sort()
for a in ans:
     print(a)
### BUGGY CODE ###

from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [-1] * (w * h)  # 前処理
    que = deque()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[j + (w * i)] = 0
                que.append((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if 0 <= i < h and 0 <= j < w and dist[j + (w * i)] < 0:
                dist[j + (w * i)] = dist[y + (w * x)] + 1
                que.append((i, j))
    return max(dist)


h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(bfs(a))


### FIXED CODE ###

from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que = deque()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if 0 <= i < h and 0 <= j < w and dist[i][j] < 0:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j))
    return dist[x][y]


h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(bfs(a))
### BUGGY CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]

players = [k for _ in range(n)]

for i in a:
    for p in range(len(players)):
        if p != i-1:
            players[p] -= 1

for p in players:
    if p > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]

players = [k-q for _ in range(n)]

for i in a:
    players[i-1] += 1

for p in players:
    if p > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(_) for _ in input().split()]
dp = [1000000000] * n
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]))
print(dp[n-1])


### FIXED CODE ###

n, k = map(int, input().split())
h = [int(_) for _ in input().split()]
dp = [1000000000] * n
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]))
print(dp[n-1])
### BUGGY CODE ###

N = int(input())
C = input()
C = C.lstrip('R').rstrip('W')

ans = 0
for i in range(10**6):
    if len(C) > 0:
        l = C.find('R')
        r = C[::-1].find('W')
        n = min(l, r)
        C = C[n:-n]
        C = C.lstrip('R').rstrip('W')
        ans += n
    else:
        break
print(ans)

### FIXED CODE ###

N = int(input())
C = input()

l, r = 0, N - 1
ans = 0
while l < r:
    if C[l] == 'R':
        l += 1
    elif C[r] == 'W':
        r -= 1
    else:
        ans += 1
        l += 1
        r -= 1
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
max_a=A[0]
dp=[True]*(max_a+1)
ans=0
for i in range(N):
  a=A.pop()
  #print(a)
  if dp[a]==True: 
    if a not in A:
      ans+=1
    k=a
    while k<=max_a:
      dp[k]=False    
      k+=a
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
max_a=A[-1]
dp=[True]*(max_a+1)
ans=0
for i in range(N):
  a=A[i]
  #print(a)
  if dp[a]==True: 
    if i==N-1:
      ans+=1
    elif a!=A[i+1]:
      ans+=1
    
    k=a
    while k<=max_a:
      dp[k]=False    
      k+=a
print(ans)
### BUGGY CODE ###

n = int(input())
A = sorted(list(map(int,input().split())))
c = 0
for i in (set(A)):
    tmp = A.count(i)
    if tmp < i:
        c += tmp
    else:
        c += tmp - i
print (c)


### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int,input().split()))
c = Counter(A)
ans = 0
for k,v in c.items():
    if v < k:
        ans += v
    else:
        ans += v-k
print (ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

a = list(set(A))
a_n = []
c = []
new = []
if len(a) != N:
  for i in range(len(a)):
    x = A.count(a[i])
    a_n.append(x)
    c.append(x*(x-1)//2)
    new.append((x-1)*(x-2)//2)

  ans = sum(c)
  for i in range(N):
    n = a.index(A[i])
    print(ans-c[n]+new[n])
else:
  for _ in range(N):
    print(0)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

a = list(set(A))
a_c = {}
for v in A:
  if v in a_c:
    a_c[v] += 1
  else:
    a_c[v] = 1

def cmb(n):
  if n < 2: return 0
  else:
    return n * (n-1)//2

S = 0
for k in a_c:
  S += cmb(a_c[k])

for i in range(N):
  print(S - cmb(a_c[A[i]]) + cmb(a_c[A[i]]-1))
### BUGGY CODE ###

from collections import defaultdict

D = defaultdict(int)

def f(x,y,z):
    return x**2+y**2+z**2+x*y+y*z+z*x
    return (x+y+z)**2+(x*y+y*z+z*x)

N=int(input())
for i in range(1,N+1):
    ans=0
    for x in range(1,101):
        for y in range(1,101):
            for z in range(1,101):
                ret = f(x,y,z)
                if ret==N:
                    ans+=1
    print(ans)


### FIXED CODE ###

from collections import defaultdict

D = defaultdict(int)

def f(x,y,z):
    return x**2+y**2+z**2+x*y+y*z+z*x
    return (x+y+z)**2+(x*y+y*z+z*x)

N=int(input())
for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            ret = f(x,y,z)
            if ret>N:
                break
            D[f(x,y,z)]+=1

for i in range(1,N+1):
    print(D[i])
### BUGGY CODE ###

import copy

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

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

for i, l in enumerate(abc):
    if i == 0:
        dp[i] = copy.deepcopy(l)
    else:
        mx = 0
        ex = [0, 1, 2]
        ext = copy.deepcopy(ex)
        for j, m in enumerate(l):
            ext.remove(j)
            mx1 = max(mx, abc[i][ext[0]] + dp[i - 1][j])
            mx2 = max(mx, abc[i][ext[1]] + dp[i - 1][j])
            mx = max(mx1, mx2)
            ext = copy.deepcopy(ex)
            dp[i][j] = mx

print(max(dp[-1]))

### FIXED CODE ###

N = int(input())
la, lb, lc = [0] * 3

for i in range(N):
    a, b, c = [int(x) for x in input().split()]
    aa = a + max(lb, lc)
    bb = b + max(lc, la)
    cc = c + max(lb, la)
    la = aa
    lb = bb
    lc = cc

print(max(la, lb, lc))
### BUGGY CODE ###

import numpy as np  # noqa

m = 998244353
N, K = map(int, input().split())

jumps = []
for i in range(K):
    l, r = map(int, input().split())
    jumps.append([l, r])

jumps = np.array(jumps)
dp2 = np.zeros(N + 1)

dp = np.zeros(N + 1)
dp[1] = dp2[1] = 1
for i in range(2, N + 1):
    for j, jump in enumerate(jumps):
        mn = max(0, i - jump[1])
        mx = max(mn, i - jump[0])
        dp[i] = (dp[i] + dp2[mx] - dp2[mn - 1]) % m
    dp2[i] = (dp[i] + dp2[i - 1]) % m

print(int(dp[N]))


### FIXED CODE ###

import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353


@njit((i8, i8[:]), cache=True)
def main(N, LR):
    L, R = LR[::2], LR[1::2]
    K = len(L)
    F = np.zeros(N + 10, np.int64)
    F[0] = 1
    for n in range(1, N + 10):
        F[n] += F[n - 1]
        for k in range(K):
            l, r = L[k], R[k] + 1
            if n - l >= 0:
                F[n] += F[n - l]
            if n - r >= 0:
                F[n] -= F[n - r]
        F[n] %= MOD
    ans = F[N - 1] - F[N - 2]
    return ans % MOD


N, K = map(int, readline().split())
LR = np.array(read().split(), np.int64)

print(main(N, LR))
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
N = int(input())
count = 0
for i in range(0,N):
    count = count + len(make_divisors(i))
print(count)

### FIXED CODE ###

N = int(input())
count = 0
for i in range(1,N):
    count = count + (N-1)//i
print(count)
### BUGGY CODE ###

N,A = map(int,input().split())
x = list(map(int,input().split()))

temp = x + [A]

X = max(temp)

m = N * X

dp = [[[0]*(m+1) for k in range(N+1)] for j in range(N+1)]

for j in range(N+1):
    for k in range(N+1):
        for s in range(m+1):
            if (j == 0) & (k == 0) & (s == 0):
                dp[j][k][s] = 1
            elif (j >= 1) & (s < x[j-1]):
                dp[j][k][s] = dp[j-1][k][s]
            elif (j >= 1) & (k >= 1) & (s >= x[j-1]):
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]

res = 0

for i in range(N):
    res += dp[N][i+1][(i+1)*A]

print(res)


### FIXED CODE ###

N,A = map(int,input().split())
x = list(map(int,input().split()))

temp = x + [A]

X = max(temp)

m = N * X

dp = [[[0 for s in range(m+1)] for k in range(N+1)] for j in range(N+1)]

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

res = 0

for j in range(N):
    for k in range(N):
        for s in range(m):
            if dp[j][k][s]:
                dp[j+1][k][s] += dp[j][k][s]
                dp[j+1][k+1][s+x[j]] += dp[j][k][s]

for k in range(1,N+1):
    res += dp[N][k][k*A]

print(res)