Harryxun/stf_run huggingface dataset:
s = input()
x, y = map(int, input().split())
a = 0
t = [[0], [0]]
n = 0
for i in range(len(s)):
    if s[i] == 'F':
        t[n][-1] += 1
    else:
        n = 1 - n
        t[n].append(0)
flag = [False, False]
z = [x, y]
for k in range(2):
    tt = t[k]
    zk = z[k]
    p = sum(tt)
    dp = [[False for _ in range(2 * p + 1)] for i in range(2)]
    i = 1
    if k == 0:
        dp[0][p + tt[0]] = True
    else:
        dp[0][p + tt[0]] = True
        dp[0][p - tt[0]] = True
    if len(tt) > 1:
        for tj in tt[1:]:
            for j in range(2 * p + 1):
                h = False
                if j >= tj:
                    h = h or dp[1 - i][j - tj]
                elif j <= 2 * p - tj:
                    h = h or dp[1 - i][j + tj]
                dp[i][j] = h
            i = 1 - i
    if dp[1 - i][zk + p]:
        flag = True
    else:
        flag = False
        break
if flag:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

from collections import defaultdict

s = input()
x, y = map(int, input().split())
a = 0
t = [[0], []]
n = 0
for i in range(len(s)):
    if s[i] == 'F':
        t[n][-1] += 1
    else:
        n = 1 - n
        t[n].append(0)
flag = [False, False]
z = [x, y]
for k in range(2):
    tt = t[k]
    zk = z[k]
    if len(tt) == 0:
        if zk == 0:
            flag = True
            continue
        else:
            print(1, k)
            flag = False
            break
    p = sum(tt)
    dp = defaultdict(bool)
    i = 1
    if k == 0:
        dp[tt[0]] = True
    else:
        dp[tt[0]] = True
        dp[-tt[0]] = True
    if len(tt) > 1:
        for tj in tt[1:]:
            dp2 = defaultdict(bool)
            for xj in dp.keys():
                dp2[xj + tj] = True
                dp2[xj - tj] = True
            dp = dp2
    flag = dp[zk]
    if not flag:
        break
if flag:
    print('Yes')
else:
    print('No')
# -*- coding: utf-8 -*-
N = int(input())
a = [input() for i in range(N)]
for i in range(N):
  if a[i][len(a[i])]=a[i+1][0]:
    continue
  else:
    break
    print("No")
print("Yes")
    

### FIXED CODE ###

N = int(input())
W = []
for i in range(N):
    W.append(str(input()))
ans = "No"
startwith = []
endwith = []
if len(set(W)) == len(W):
   for i in W:
       startwith.append(i[0])
       endwith.append(i[-1])
   startwith.pop(0)
   endwith.pop(-1)
   if startwith == endwith:
    ans = "Yes"

print(ans)
a,b=map(int,input().split())
list_a=list(map(int,input().split()))
list_b=x for x in list_a if x>=b
print(len(list_b))

### FIXED CODE ###

a,b=map(int,input().split())
i=list(map(int,input().split()))
j=[x for x in i if x>=b]
print(len(j))
n = int(input())
a = list(map(int, input().split()))

n2 = 0
n4 = 0

for ai in a:
  if ai % 4 == 2:
    n2 += 1
  if ai % 4 == 0:
    n4 += 1

if not n2 and n4:
  n2 += l
if n2 + n4 * 2 >= n:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

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

n2 = 0
n4 = 0

for ai in a:
  if ai % 4 == 2:
    n2 += 1
  if ai % 4 == 0:
    n4 += 1

if n2 == 0 and n4:
  n2 += 1
if n2 + n4 * 2 >= n:
  print('Yes')
else:
  print('No')
n,x=map(int,input().split())
a=list(map(int,input().split()))
ar=a.sort(reverse=True,key=int)
ans=0
for i in range(n):
  x-=ar[i]
  if x<0:
    x+=ar[i]
  else:
    ans+=1
print(ans)
  

### FIXED CODE ###

n,x=map(int,input().split())
a=list(map(int,input().split()))
a.sort(key=int)
ans=0
for i in range(n):
  x=x-a[i]
  if x<0:
    x=x+a[i]
  else:
    ans+=1
if ans==n:
    if x>0:
        print(ans-1)
    else:
        print(ans)
else:
    print(ans)
import math
a,b,c=map(int, input().split())
msg= "Yes" if math.sqrt(a)+math.sqrt(b)<math.sqrt(c) else "No"
print(msg)

### FIXED CODE ###

import sys

lst=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
pos = input()
print(lst[int(pos)-1])
N, K = input().split()
N = int(N)
K = int(K)
S = input()
A = []
for i in range(len(S)-1):
    if (S[i]=="0" and S[i+1]=="1") or (S[i]=="1" and S[i+1]=="0"):
        A.append(i+1)
A.insert(0, 0)
A.append(N)
if len(A) == 2:
    print(len(S))
else:
    M = []
    while K > 0:
        if S[0] == "0":
            M.append(A[K*2]-A[0])
            a = 1
            b = a + K*2 + 1
        elif S[0] == "1":
            a = 0
            b = a + K*2 + 1
        if S[-1] == "1":
            while b <= len(A):
                M.append(A[b]-A[a])
                a += 2
                b = a + K*2 + 1
        elif S[-1] == "0":
            while b <= len(A)-1:
                M.append(A[b]-A[a])
                a += 2
                b = a + K*2 + 1
            M.append(A[-1]-A[-1-K*2])
        K -= 1
    print(max(M))

### FIXED CODE ###

N, K = input().split()
N = int(N)
K = int(K)
S = input()
A = []
for i in range(len(S)-1):
    if (S[i]=="0" and S[i+1]=="1") or (S[i]=="1" and S[i+1]=="0"):
        A.append(i+1)
A.insert(0, 0)
A.append(N)
M = []
if S == "0"*N:
    M.append(len(S))
elif S[0] == "0":
    if K > len(A)//2:
        K = len(A)//2
    M.append(A[K*2]-A[0])
    a = 1
    b = a + K*2 + 1
elif S[0] == "1":
    if K > (len(A)-1)//2:
        K = (len(A)-1)//2
    a = 0
    b = a + K*2 + 1
if S == "0"*N:
    pass
elif S[-1] == "1":
    while b <= len(A):
        M.append(A[b]-A[a])
        a += 2
        b = a + K*2 + 1
elif S[-1] == "0":
    while b <= len(A)-1:
        M.append(A[b]-A[a])
        a += 2
        b = a + K*2 + 1
    M.append(A[-1]-A[-1-K*2])
print(max(M))
#!/usr/bin/env python3

from collections import deque
H, W = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)

done = [[True for _ in range(W)] for _ in range(H)]
ans = [[-1 for _ in range(W)] for _ in range(H)]

q = deque([(0, 0, 1)])
color = 1

while q:
    x, y, color = q.pop()
    if A[color] > 0:
        ans[x][y] = color
        A[color] -= 1
    else:
        color += 1
        ans[x][y] = color
        A[color] -= 1

    for i, j in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        x_next = x + i
        y_next = y + j
        if (0 <= x_next and x_next < H 
        and 0 <= y_next and y_next < W
        and done[x_next][y_next] is True):
            q.append((x_next, y_next, color))

[print(" ".join(map(str, a))) for a in ans]

### FIXED CODE ###

H, W = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)

ans = [[-1 for _ in range(W)] for _ in range(H)]
color = 1

for i in range(H):
    for j in range(W):
        if A[color] == 0:
            color += 1
        A[color] -= 1
        ans[i][j] = color

for i in range(H):
    a = ans[i]
    if i % 2 == 1:
        a = a[::-1]
    print(" ".join(map(str, a)))
A = int(input())
B = int(input())
C = int(input())
a = 10*A + B
b = 10*B + C
print(max([a+C ,A+b]))

### FIXED CODE ###

suuji = list(map(int, input().split()))
saidai = max(suuji)
suuji.remove(saidai)
print(saidai*10+suuji[0]+suuji[1])
import itertools
N,M=map(int,raw_input().split())
data=[map(float,raw_input().split()) for i in range(N)]
maxV=0.0
for comb in itertools.permutations(range(N),M):
    dist=0.0
    for i in range(M-1):
        for j in range(i+1,M):
            t=comb[i]
            s=comb[j]
            dist+=pow(data[t][0]-data[s][0],2)+pow(data[t][1]-data[s][1],2)+pow\
(data[t][2]-data[s][2],2)
    maxV=max(maxV,dist)
print maxV

### FIXED CODE ###

import itertools
N,M=map(int,raw_input().split())
data=[map(float,raw_input().split()) for i in range(N)]
maxV=0.0
for comb in itertools.combinations(range(N),M):
    dist=0.0
    for i in range(M-1):
        for j in range(i+1,M):
            t=comb[i]
            s=comb[j]
            dist+=pow(data[t][0]-data[s][0],2)+pow(data[t][1]-data[s][1],2)+pow\
(data[t][2]-data[s][2],2)
    maxV=max(maxV,dist)
print maxV
# coding: utf-8
 
n, m, x, y = map(int, input().split())
xn = list(map(int, input().split()))
ym = list(map(int, input().split()))
 
if x < y:
    for i in range(x, y+1)
        if max(xn) < i and min(ym)>=i:
            print("War")
        elif i = y:
            print("No War")
else:
    print("No War")

### FIXED CODE ###

# coding: utf-8
 
n, m, x, y = map(int, input().split())
xn = list(map(int, input().split()))
ym = list(map(int, input().split()))
xn.append(x)
ym.append(y)
flag = 0

if max(xn) < min(ym):
    print("No War")
else:
    print("War")
N,D = map(int,input().split())
A=[]
C=0
D=0
E=0
for i in range (1,N+1):
    A.append(i)
for i in range (0,N):
    A[i]=list(map(int,input().split()))
for i in range (0,N-1):
    for j in range(i,N-1):
        for k in range(0,D):
            B=(A[j][k]-A[j+1][k])**2
            C+=B
        D=C
        C=0
        if ((D)**(1/2))%1 ==  (D)**(1/2):
            E+=1
print(E)









### FIXED CODE ###

N, A, B = map(int,input().split())
if B<N*A :
    print(B)
else :
    print(N*A)
X=int(input())
A=0
G=0
N=0
M=0
Z=0
N=X/500
M=int(X%500)
Z=M/5
N=N+Z
for i in range(0,N):
    if X-500:
        X=X-500
        G=G+1000
    elif X-5:
        X=X-5
        G=G+5
    else:
        break
        
print(G)
        
    

### FIXED CODE ###

X=int(input())
A=0
G=0
N=0
M=0
Z=0
N=int(X/500)
M=int(X%500)
Z=int(M/5)
N=N+Z
for i in range(0,N):
    if X>=500:
        X=X-500
        G=G+1000
    elif X>=5:
        X=X-5
        G=G+5
    else:
        break
        
print(G)
n, a, b = map(int, input().split())
s = ""
while len(s) < n:
  s += "b" * a + "r" * b
print(s[:n].count("b"))
    

### FIXED CODE ###

n, a, b = map(int, input().split())
s = n // (a + b)
t = n % (a + b)
print(s * a + min(t, a))
a = input()
print(a ** 3)


### FIXED CODE ###

a = int(input())
print(a ** 3)
friends=input()
friends.split(' ')
friends_all=friends[0]
cakes=input()
cakes_amount(sum(cakes.split(' ')))
one_person=cakes_amount//friends_all
if cakes_amount%friends_all==0:
        pass
else:
        one_person+=1
preint(one_person)



### FIXED CODE ###

friends=input()
friends=friends.split()
friends_all=friends[0]
person=int(friends_all)+1
cakes=input()
cakes_amount=0
for a in cakes.split():
        cakes_amount+=int(a)
one_person=cakes_amount//person

if cakes_amount%person!=0:
        one_person+=1
else:
        pass
print(one_person)
n,k=map(int,input().split())
print(k*(k-1)**(n-1))

### FIXED CODE ###

a =list(map(int, input(). split()))
print(len(set(a)))
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))

whole = a.sum()
div = np.abs(a.cumsum() - whole / 2).argmin()

if div == 0 or div == (n - 1):
    print(min(np.abs(a[0] - a[1:].sum()), np.abs(a[:-1] - a[-1].sum())))
else:
    print(np.abs(a[:div + 1].sum() - a[div + 1:].sum()))

### FIXED CODE ###

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

whole = sum(a)

if n == 2:
    print(abs(a[0] - a[1]))
else:
    now = 0
    ans = float("inf")
    for i in a[:-1]:
        now += i
        diff = abs(whole - 2 * now)
        ans = min(ans, diff)

    print(ans)
import sys
sys.setrecursionlimit(10**9)
input = lambda:sys.stdin.readline().rstrip()

def Warshall_Floyd(d):
    #dist[i][j]:iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d
############################
n, m, l = map(int, input().split())
f_inf = float('inf')
dist = [[f_inf]*n for _ in range(n)]
for i in range(m): dist[i][i] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c

dist = Warshall_Floyd(dist)

dist2 = [[f_inf]*n for _ in range(n)]
for i in range(m): dist2[i][i] = 0
for i in range(n):
    for j in range(n):
        if dist[i][j] <= l:
            dist2[i][j] = 1

dist2 = Warshall_Floyd(dist2)

q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    ans = dist2[s-1][t-1]
    if dist2[s-1][t-1] == f_inf:
        print(-1)
    else:
        print(ans-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M, L = map(int, input().split())
    dist = [[float('inf')] * N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        if C > L:
            continue
        A -= 1
        B -= 1
        dist[A][B] = C
        dist[B][A] = C

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    e = [[float('inf')] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if dist[i][j] <= L:
                e[i][j] = 1
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                e[i][j] = min(e[i][j], e[i][k] + e[k][j])


    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        if e[s][t] == float('inf'):
            print(-1)
            continue
        ans = e[s][t]
        print(ans-1)


if __name__ == "__main__":
    main()
N = int(input())
print (N*(N+1)//2 - 3*(N//3)((N//3)+1)//2 - 5*(N//5)((N//5)+1)//2 + 15*(N//15)((N//15)+1)//2)

### FIXED CODE ###

N = int(input())
print (N*(N+1)//2 - 3*(N//3)*((N//3)+1)//2 - 5*(N//5)*((N//5)+1)//2 + 15*(N//15)*((N//15)+1)//2)
a = [0,0,0,0,0,0,0,0,0,0]

a = 0
a[0] = int(input())

for i in range(9):
  while a[i] != 0:
    a[i+1] += a[i] % 10
    a[i] = a[i] // 10 


if a[9] % 9 == 0:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

a = 0
s = input()
for c in s:
  a += int(c)

if a % 9 == 0:
  print('Yes')
else:
  print('No')
import bisect
def solve():
  n,c,k = (int(i) for i in input().split())
  t = [int(input()) for i in range(n)]
  t = sorted(t,reverse = True)
  ans = 0
  
  while t:
    ans += 1
    customer = t.pop(0)
    if len(t) >= 1:
     for i in range(c-1):
      if customer  <= t[0] + k:
        t.pop(0)
      else:
        break
  print(ans)
  
solve()

### FIXED CODE ###

import bisect
def solve():
  n,c,k = (int(i) for i in input().split())
  t = [int(input()) for i in range(n)]
  t = sorted(t,reverse = True)
  ans = 0
  
  while t:
    ans += 1
    customer = t.pop(0)
    if len(t) >= 1:
     for i in range(c-1):
      if customer  <= t[0] + k:
        t.pop(0)
      else:
        break
      if len(t) == 0:
        break
  print(ans)
  
solve()
import math
num=list(input().split())
A=num[0]
B=num[1]
print(A*B//math.gcd(A,B))

### FIXED CODE ###

def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a
def lcm(a,b):
  return a*b//gcd(a,b)

num=list(map(int,input().split()))
A=num[0]
B=num[1]
S=lcm(A,B)
print(S)
def fibonacci(n):
    if n==-1:
        return 0
    if n==1 or n==0:
        return 1
    else:
        return fibonacci(n-1)+fibonacci(n-2)

N,M=map(int,input().split())
a=[]
for _ in range(0,M):
    a.append(int(input()))
a.append(N+1)
m=1
for i in range(0,M+1):
    if i==0:
        m=fibonacci(a[i]-1)
    else:
        m=m*fibonacci(a[i]-a[i-1]-2)

print(m%(10**9+7))


### FIXED CODE ###

def fibonacci(n):
    if n<0:
        return 0
    else:
        a=1
        b=1
        if n==0:
            return a
        elif n==1:
            return b
        else:
            i=n-2
            while i>=0:
                x=a
                a=b
                b=x+b
                i=i-1
            return b

N,M=map(int,input().split())
a=[]
for _ in range(0,M):
    a.append(int(input()))
a.append(N+1)
m=1
for i in range(0,M+1):
    if i==0:
        m=fibonacci(a[i]-1)
    else:
        m=m*fibonacci(a[i]-a[i-1]-2)

print(m%(10**9+7))
rgb = int(input())

if (rgb % 4 == 0):
    print("YES")
else:
    print("NO")

### FIXED CODE ###

r, g, b = map(int , input().split())

rgb = 100*r + 10*g + b

if (rgb % 4 == 0):
    print("YES")
else:
    print("NO")
k = int(input())
a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(a[k + 1])

### FIXED CODE ###

a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = int(input())
print(a[K-1])
n,k=map(int,input().split())
dis = 1
for i in range(n):
    if dis*2 <= dis+k:
        dis *= 2
    else:
        dis += k
print(dis)

### FIXED CODE ###

n=int(input())
k=int(input())
dis = 1
for i in range(n):
    if dis*2 <= dis+k:
        dis *= 2
    else:
        dis += k
print(dis)
import math
x,y = map(str,input().split())
y=int(float(y)*100)
a=int(x)*y

a=int(str(a)[:-2])
print(a)

### FIXED CODE ###

from decimal import *
a,b=input().split()
a=Decimal(a)
b=Decimal(b)
ans=int(a*b)
print(ans)
import numpy as np
N = int(input())

ARR = []

for i in range(N):
    ARR.append([int(s) for s in input().split(" ")])

PRR = []

for i in range(N):
    PRR.append([int(s) for s in input().split(" ")])

def calculate(n, arr, prr):
    

    return []

result = calculate(N, ARR, PRR)
print(max(result))



### FIXED CODE ###

n = int(input())

frr = []

for i in range(n):
    frr.append([int(s) for s in input().split(" ")])

prr = []

for i in range(n):
    prr.append([int(s) for s in input().split(" ")])

# n = 2
#
# frr = [
#     [1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
#     [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
# ]
#
# prr = [
#     [0, -2, -2, -2, -2, -2, -1, -1, -1, -1, -1],
#     [0, -2, -2, -2, -2, -2, -1, -1, -1, -1, -1]
# ]


res = []
for i in range(1,2 ** 10):
    count = [0 for s in range(n)]

    mask = []
    for j in range(10):
        m =  i >> j & 1
        mask.append(m)
        if m == 1:
            for k in range(n):
                if frr[k][j] == 1:
                    count[k] = count[k] + 1

    mm = []
    for index,c in enumerate(count):
        mm.append(prr[index][c])

    res.append(sum(mm))

print(max(res))
n=int(input())
ball_xy = []
for _ in range(n):
    x, y = (int(x) for x in input().split())
    ball_xy.append([x, y])

distance = {}

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if (ball_xy[i][0]-ball_xy[j][0], ball_xy[i][1]-ball_xy[j][1]) in distance:
            distance[(ball_xy[i][0]-ball_xy[j][0], ball_xy[i][1]-ball_xy[j][1])] += 1
        else:
            distance[(ball_xy[i][0]-ball_xy[j][0], ball_xy[i][1]-ball_xy[j][1])] = 1

cost_0 = max(distance.values())

print(n-cost_0)

### FIXED CODE ###

n=int(input())

if n == 1:
    print(1)
    exit()

ball_xy = []
for _ in range(n):
    x, y = (int(x) for x in input().split())
    ball_xy.append([x, y])

distance = {}

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if (ball_xy[i][0]-ball_xy[j][0], ball_xy[i][1]-ball_xy[j][1]) in distance:
            distance[(ball_xy[i][0]-ball_xy[j][0], ball_xy[i][1]-ball_xy[j][1])] += 1
        else:
            distance[(ball_xy[i][0]-ball_xy[j][0], ball_xy[i][1]-ball_xy[j][1])] = 1

cost_0 = max(distance.values())

print(n-cost_0)
N, M, X, Y = map(int, input().split())
list1 = [int(input()) for i in range(N)]
list2 = [int(input()) for h in range(M)]

if X >= min(list1) or Y <= max(list2):
  print("War")
  
else:
  print("No War")

### FIXED CODE ###

n,m,X,Y = map(int,input().split())
x = list(map(int,input().split()))
y = list(map(int,input().split()))
x.append(X)
y.append(Y)
x.sort()
y.sort()
print('No War' if x[-1] < y[0] else 'War')
import sys

def main():
    N = sys.stdin.readline()
    w = ['Sunny', 'Cloudy', 'Rainy', 'Sunny']
    i = w.index(N)
    print(w[i+1])

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys

def main():
    N = sys.stdin.readline().rstrip()
    w = ['Sunny', 'Cloudy', 'Rainy']
    i = w.index(N)
    print(w[(i+1)%3])

if __name__=='__main__':
    main()
import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

X = input_int()

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        return 2
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            return f
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
        return n
    return n

A_B = prime_factorize(X)
A = 1
while True:
    B = A - A_B
    num = A ** 4 + A ** 3 * B + A ** 2 * B ** 2 + A * B ** 3 + B ** 4
    if X % num == 0:
        print(A, B)
        return
    A += 1

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

X = input_int()

for a in range(2000):
    A = a - 1000

    for b in range(2000):
        B = b - 1000
        if A ** 5 - B ** 5 == X:
            print("{} {}".format(A, B))
            exit()
N = int(input())
arares = list(map(int, input().split()))
four = False
for arare in arares:
  if arare == 'Y':
    four = True
    break
if four:
  print('Four')
else:
  print('Three')

### FIXED CODE ###

N = int(input())
arares = list(input().split())
four = False
for arare in arares:
  if arare == 'Y':
    four = True
    break
if four:
  print('Four')
else:
  print('Three')
n=int(input())
l=[]
for i in range(n):
  s=int(input())
  l.append(s)
 
 
a=int(round(sum(l)/n))
k=0
for j in l:
  k = k + (j-a)**2
print(k)


### FIXED CODE ###

n=int(input())
l= list(int(i) for i in input().split())
a=int(round(sum(l)/n))
k=0
for j in l:
  k = k + (j-a)**2
print(k)
import math
A,B=map(int,input().split())
Ms = int(math.log2(B))
ms = int(math.log2(A))+1
binary=0
for x in range(A,2**ms):
    binary = binary^x

for x in range(2**Ms,B+1):
    binary = binary^x

print(binary)

### FIXED CODE ###

import math
A,B=map(int,input().split())
x=0
if A%2==0:#偶数スタート
    if(B%2==0):#偶数エンド
        if((B-A)/2 %2 == 0 ):#1が偶数個ならば？
            print(B)
        else:
            print(1^B)
    else:#奇数エンド
        if(((B+1) - A)/2 %2 == 0):#1が偶数個ならば？
            print(0)
        else:
            print(1)
else:#奇数スタート
    if(B%2==0):#偶数エンド
        if((B-(A+1))/2 %2 ==0):
            print(A^B)
        else:
            print(A^B^1)
    else:#奇数エンド
        if((B-A)/2 %2 == 0):
            print(A)
        else:
            print(A^1)
n,v=[int(k) for k in input().split()]
li=[]
for i in range(n):
  li.append([int(k) for k in input().split()])
  
dp=[[0 for i in range(v+1)] for j in range(n+1)]
for a in range(1,n+1):
  for b in range(1,v+1):
    if(li[a-1][0]<=b):
      dp[a][b]=max(li[a-1][1]+dp[a-1][b-li[a-1][0]],dp[a-1][b])
    else:
      dp[a][b]=dp[a-1][b]
print(dp[n][v])      
      
  


### FIXED CODE ###

n=int(input())
li=[]
for i in range(n):
  li.append([int(k) for k in input().split()])
dp=[[0 for i in range(3)] for j in range(n)]
dp[0]=li[0]

for j in range(1,n):
    for i in range(3):
        if(i==0):
            dp[j][i]=li[j][i]+max(dp[j-1][i+1],dp[j-1][i+2])
        elif(i==1):
            dp[j][i]=li[j][i]+max(dp[j-1][i-1],dp[j-1][i+1])
        elif(i==2):
            dp[j][i]=li[j][i]+max(dp[j-1][i-1],dp[j-1][i-2])    
       
#print(dp)
print(max(dp[n-1]))