Harryxun/stf_run huggingface dataset:
N = int(input())
T = []
X = []
Y = []
T[0] = X[0] = Y[0] = 0
for i in range(N):
    t,x,y = map(int,input().split())
    T.append(t)
    X.append(x)
    Y.append(y)

flag = True
for i in range(N):
    time = T[i+1]-T[i]
    dist = abs(X[i+1]-X[i])+abs(Y[i+1]-Y[i])
    if time < dist or (dist%2!=time%2):
        flag = False
        break
if flag:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

N = int(input())
T = [0]
X = [0]
Y = [0]
for i in range(N):
    t,x,y = map(int,input().split())
    T.append(t)
    X.append(x)
    Y.append(y)

flag = True
for i in range(N):
    time = T[i+1]-T[i]
    dist = abs(X[i+1]-X[i])+abs(Y[i+1]-Y[i])
    if time < dist or (dist%2!=time%2):
        flag = False
        break
if flag:
    print('Yes')
else:
    print('No')
import functools
import operator
S=int(input())
prod = functools.partial(functools.reduce, operator.mul)
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct
SS=factorize(S)
if len(SS)>1:
    print(0,0,prod(SS[1::2]),0,0,prod(SS[0::2]))
else:
    print(0,0,SS[0],0,0,1)

### FIXED CODE ###

import math
S=int(input())
X1,Y1=0,0
X2=math.ceil(math.sqrt(S))
Y3=X2
Y2=1
X3=X2*Y3-S
print(X1,Y1,X2,Y2,X3,Y3)
N,L=map(int,input().split())
S=[input() for i in range(N)] 
S.sorted()
for i in range(len(S)):
    print(S[i])

### FIXED CODE ###

n,l=map(int,input().split())
s=sorted([input() for i in range(n)])
print(*s,sep="")
def main():
    n = int(input())
    a = sorted(map(int, input().split()))

    c = n // 2
    for i in range(n):
        if i < c:
            print(a[c])
        else:
            print(a[c - 1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, m, x = map(int, input().split())
    a = map(int, input().split())

    cost_move_to_left = 0
    cost_move_to_right = 0
    for i in a:
        if i > x:
            cost_move_to_left += 1
        elif i < x:
            cost_move_to_right += 1

    print(cost_move_to_left if cost_move_to_left < cost_move_to_right else cost_move_to_right)



if __name__ == '__main__':
    main()
N, M = map(int, input().split())
for _ in range(M):
    p, S = input().split()
p = map(int, p)

flag_p = p[0]
flag_ac = 0
AC_sum = 0
WA_sum = 0

for i in range(M):
  if flag_p == p[i]:
    if S[i] == 'WA':
      WA += 1
    elif S[i] == 'AC' and flag_ac == 0:
      AC_sum += 1
      WA_sum += WA
      flag_ac = 1
      
  else:
    WA = 0
    flag = p[i]
    if S[i] == 'WA':
      WA += 1
    elif S[i] == 'AC' and flag_ac == 0:
      AC_sum += 1
      WA_sum += WA
      flag_ac = 1
    
print(AC_sum. WA_sum)

### FIXED CODE ###

import sys

N, M = map(int, input().split())
if M == 0:
    print(0, 0)
    sys.exit()

p_S = []
for _ in range(M):
    p_S.append(input().split())
    
p = []
S = []


for i in range(M):
    p_S[i][0] = int(p_S[i][0])
    p_S[i][1] = int(p_S[i][1] =='AC')
    
p_S.sort(key=lambda x: x[0])

for i in range(M):
    p.append(p_S[i][0])
    S.append(p_S[i][1])

p = list(map(int, p))
S = list(map(int, S))

flag_p = p[0]
flag_ac = 0
AC_sum = 0
WA_sum = 0
WA = 0

for i in range(M):

    if flag_p == p[i]:
        if S[i] == 0 and flag_ac == 0:
            WA += 1
        elif S[i] == 1 and flag_ac == 0:
            AC_sum += 1
            WA_sum += WA
            flag_ac = 1
    else:
        flag_p = p[i]
        flag_ac = 0
        WA = 0
        if S[i] == 0 and flag_ac == 0:
            WA += 1
        elif S[i] == 1 and flag_ac == 0:
            AC_sum += 1
            WA_sum += WA
            flag_ac = 1

print(AC_sum, WA_sum)
N,M=input().split(" ")
N=(int)(N)
M=(int)(M)

sc={}

for i in range(M):
    sc[i]=-1

check=True

for i in range(M):
    si,ci = input().split(" ")
    si = (int)(si)
    ci = (int)(ci)
    if sc[si-1]!=-1 and sc[si-1]!=ci:
        check = False
        break
    else:
        sc[si-1]=ci
#print(si)
if check and sc[0]!=0:
    ans=""
    if sc[0]==-1:
        ans+= "1"
    else:
        ans+=str(sc[0])
    
    for i in range(M-1):
        if sc[i+1]==-1:
            ans+="0"
        else:
            ans+=(str)(sc[i+1])
    print(ans)
else:
    print(-1)

### FIXED CODE ###

N,M=(input()).split(" ")
N=(int)(N)
M=(int)(M)
sc={}

for i in range(N):
    sc[i]=-1

check=True

for i in range(M):
    s,c=(input()).split(" ")
    s=(int)(s)
    c=(int)(c)
    if sc[s-1]!=-1 and sc[s-1]!=c:
        check = False
        break
    else:
        sc[s-1]=c

if not(check):
    print(-1)
    exit()

if N!=1:
    

    ans=""
    if sc[0]==-1:
        ans+="1"
    elif sc[0]==0:
        print(-1)
        exit()
    else:
        ans+=str(sc[0])

    for i in range(N-1):
        if sc[i+1]==-1:
            ans+="0"
        else:
            ans+=str(sc[i+1])
    print(ans)
else:
    if sc[0]==-1:
        print(0)
    else:
        print(sc[0])
# -*- coding: utf-8 -*-
import numpy as np 
import math

# 入力
N = int(input())
A = input()

A = np.array(A.split()).astype('int')
ones = np.ones([N, N])
B = (A*ones)
for i in range(N):
    B[i, i] = 0
B = B[np.where(B != 0, True, False)].reshape(N, N-1)
B.sort()

def comb(n, r):
    if n < r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
      
def uniq_2_comb(N, ar):
    u = np.unique(ar, return_index=True)[1]
    u = np.concatenate([u, np.array([N-1])])
    ans = 0
    for i in range(len(u)-1):
        n = u[i+1] - u[i]
        ans += comb(n, 2)
    return ans

#ans_ar = np.apply_along_axis(lambda x : uniq_2_comb(N, x), 1, B)
for i in range(len(B)):
    print(uniq_2_comb(N, B[i]))
  

#for a in ans_ar:
#    print(a)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections
import math

# 入力
N = int(input())
A = list(input().split())

c = collections.Counter(A)

def comb(n, r):
    if n < r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

comb_sum = 0
for i in c:
    comb_sum += comb(c[i], 2)
     
for a in A:
    ans = comb_sum
    if c[a] >= 2:
        ans -= (c[a] - 1)
    print(ans)
import numpy as np
N, M = [int(a) for a in input().split()]
P = []
Y = []

for _ in range(M):
    p, y =  [int(a) for a in input().split()]
    P.append(p)
    Y.append(y)

index = [1 for _ in range(len(P))]
id = ["" for _ in range(len(P))]

for i in np.argsort(Y):
    id[i] = "{0:06d}".format(P[i])+"{0:06d}".format(index[P[i]])
    index[P[i]] += 1

for i in id:
    print(i)

### FIXED CODE ###

import numpy as np
N, M = [int(a) for a in input().split()]
P = []
Y = []

for _ in range(M):
    p, y =  [int(a) for a in input().split()]
    P.append(p)
    Y.append(y)

index = {}
id = ["" for _ in range(len(P))]

for i in np.argsort(Y):
    index[P[i]] = index.get(P[i], 1)
    id[i] = "{0:06d}".format(P[i])+"{0:06d}".format(index[P[i]])
    index[P[i]] += 1

for i in id:
    print(i)
i=input;i()
i(sum([len(bin(a&-a))-3 for a in map(int,i().split())]))


### FIXED CODE ###

input()
print(sum(map(lambda a:len(bin(int(a)&-int(a)))-3,input().split())))
N , M = map(int,input().split())

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

A.sort()

conv = []

for i in range(M) :
    B , C = map(int,input().split())
    conv.append([B,C])

sec = lambda A : A[1]
conv.sort(key=sec,reverse=True)

change = []
add = 0

# 大きいものからN個とる
for c in conv :
    for i in range(c[0]) :
        change.append(c[1])
        add += 1

    if(add >= N) :
        break

for i in range(len(change)) :
    if A[i] >= change[i] :
        break
    A[i] = change[i]

print(int(sum(A)))

### FIXED CODE ###

N , M = map(int,input().split())

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

A.sort()

conv = []

for i in range(M) :
    B , C = map(int,input().split())
    conv.append([B,C])

sec = lambda A : A[1]
conv.sort(key=sec,reverse=True)

change = []
add = 0

# 大きいものからN個とる
for c in conv :
    for i in range(c[0]) :
        change.append(c[1])
        add += 1

    if(add >= N) :
        break

for i in range(min(N,len(change))) :
    if A[i] >= change[i] :
        break
    A[i] = change[i]

print(int(sum(A)))
from math import sqrt
x1,x2,y1,y2=map(double, print().split())
a=abs(x1-y1)
b=abs(x2-y2)
s=sqrt(a+b)
print(s)


### FIXED CODE ###

from math import sqrt
x1,x2,y1,y2=map(float,input().split())
a=abs(x1-y1)**2
b=abs(x2-y2)**2
s=sqrt(a+b)
print(s)
# ABC が開催された次の週には ARC が開催され、ARC が行われた次の週には ABC が開催
# 先週開催されたコンテストを表す文字列Sが与えられる
# 制約: S は ABC または ARC
# S = 'ABC'

if S == 'ABC':
    print('ARC')
else:
    print('ABC')

### FIXED CODE ###

# ABC が開催された次の週には ARC が開催され、ARC が行われた次の週には ABC が開催
# 先週開催されたコンテストを表す文字列Sが与えられる
# 制約: S は ABC または ARC
# S = 'ABC'

S = input()

if S == 'ABC':
    print('ARC')
else:
    print('ABC')
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
L=[0]*100000
for i in range(1,100000):
    a=A.count(i)
    L[i]=a
ans=sum(A)
for _ in range(Q):
    B,C=map(int,input().split())
    ans+=L[B]*(C-B)
    L[C]+=L[B]
    L[B]=0
    print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))
C = Counter(A)
ans = sum(A)
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    if c not in C.keys():
        C[c] = 0
    if b in C.keys():
        ans += (c-b)*C[b]
        C[c] += C[b]
        C[b] = 0
    print(ans)
n = int(input())
a = [int(i) for i in input().split()]

val = []

for i in range(n):
    val.append(a[i]-i)

val.sort()
#print(val)

#idx = [(val[0],0)]
idx = []
cnt = 1
for i in range(n-1):
    if val[i] == val[i+1]:
        #cnt += 1
        if i == n-2:
            idx.append((val[i],i+2))
        continue
    else:
        if i == n-2:
            idx.append((val[i],i+1))
            idx.append((val[i+1],i+2))
        else:
           idx.append((val[i],i+1)) 
        #cnt = 1
        
ans_val = 0
ans2_val = 0
ans3_val = 0

flag2 = False
flag3 = False

for i in range(len(idx)):
    if idx[i][1] >= (n) // 2:
        ans_val = idx[i][0]
        
        #print(i-1)
        if i-1 >= 0:
            flag2 = True
            ans2_val = idx[i-1][0]
        
        if i+1 <= n-1:
            flag3 = True
            ans3_val = idx[i+1][0]
        
        break

#print(idx,ans_val,ans2_val)
#exit()
     
ans = 0
ans2 = 0
ans3 = 0
for i in range(n):
    ans += abs(a[i]-ans_val-i)
    ans2 += abs(a[i]-ans2_val-i)
    ans3 += abs(a[i]-ans3_val-i)
    

print(min(ans,ans2,ans3))

### FIXED CODE ###

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

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

val = []

for i in range(n):
    val.append(a[i]-i)

val.sort()
#print(val)

#idx = [(val[0],0)]
idx = []
cnt = 1
for i in range(n-1):
    if val[i] == val[i+1]:
        #cnt += 1
        if i == n-2:
            idx.append((val[i+1],i+2))
        continue
    else:
        if i == n-2:
            idx.append((val[i],i+1))
            idx.append((val[i+1],i+2))
        else:
           idx.append((val[i],i+1)) 
        #cnt = 1
        
ans_val = 0
ans2_val = 0
ans3_val = 0

flag2 = False
flag3 = False

for i in range(len(idx)):
    if idx[i][1] >= (n+1) // 2:
        ans_val = idx[i][0]
        """
        #print(i-1)
        if i-1 >= 0:
            flag2 = True
            ans2_val = idx[i-1][0]
        
        if i+1 <= len(idx)-1:
            flag3 = True
            ans3_val = idx[i+1][0]
        """
        break

#print(idx,ans_val,ans2_val)
#exit()
     
ans = 0
ans2 = 10**20
ans3 = 10**20
for i in range(n):
    ans += abs(a[i]-ans_val-i)
    if flag2 == True:
        ans2 += abs(a[i]-ans2_val-i)
    if flag3 == True:
        ans3 += abs(a[i]-ans3_val-i)
    


print(ans)
a,b = map(ont,input().split())
if a+b < 10:
  print(a+b)
else:
  print('error')

### FIXED CODE ###

a,b = map(int,input().split())
if a+b < 10:
  print(a+b)
else:
  print('error')
for i in range(input()):
	ax,ay,bx,by,cx,cy,dx,dy = map(float, raw_input().split())
	ab = (ay - by) / (ax - bx)
	cd = (cy - dy) / (cx - dx)
	if ab == cd:
		print "YES"
	else:
		print "NO"

### FIXED CODE ###

for i in range(int(input())):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(float, input().split())
    if abs((y1 - y2) * (x3 - x4) - (y3 - y4) * (x1 - x2)) < 1.e-10:
        print('YES')
    else:
        print('NO')
from fractions import gcd
import math
n = int(input())
a = list(map(int, input().split()))
def lcm(a, b):
    return (a * b) // gcd(a, b)
m = 1
for x in a:
    m = lcm(m, x)
# print(m)
MOD = 1000000007
ans = 0
for x in a:
    b = m / x
    ans = (ans + b) % MOD
print(math.floor(ans))


### FIXED CODE ###

import sys
input = sys.stdin.readline
from fractions import gcd
import math
n = int(input())
a = list(map(int, input().split()))
def lcm(a, b):
    return (a * b) // gcd(a, b)
m = 1
for x in a:
    m = (m * x) // gcd(m, x)
# print(m)
MOD = 1000000007
ans = 0
for x in a:
    b = m // x
    ans = ans + b
ans = ans % MOD
print(math.floor(ans))
a,b = map(int, input().split)
print(a*b,2*a+2*b)


### FIXED CODE ###

a,b = map(int, input().split())
print(a*b,2*a+2*b)
S = input()
K = int(input())
a = list(set(S))
a.sort()

k = []
l = 0
while True:
    for i in range(len(S)):
        if S[i] == a[l]:
            for j in range(1,6):
                if i+j <= len(S):
                    k.append(S[i:i+j])
                else:
                    break
    if len(k) >= 5:
        break
    if l == len(a)-1:
        break
    l += 1

k = list(set(k))
k.sort()
print(k[K-1])

### FIXED CODE ###

S = input()
K = int(input())
a = list(set(S))
a.sort()

k = []
l = 0
while l < len(a):
    for i in range(len(S)):
        if S[i] == a[l]:
            for j in range(1,6):
                if i+j <= len(S):
                    k.append(S[i:i+j])
                else:
                    break
    l += 1

k = list(set(k))
k.sort()
print(k[K-1])
#!/usr/bin/env python3

import math
x = int(input())

#aもbも0以上のとき
border = 1;
while border ** 5 - (border - 1) ** 5 < x:
    border += 1

for i in range(border + 1):
    aa = ((x + i ** 5) ** (1.0 / 5.0)) #仮
    if aa % 1 == 0:
        a = int(aa)
        b = i
        print(a, b)
        break
else:
    b = -1
    while True:
        aa = ((x + b ** 5) ** (1.0 / 5.0))  # 仮
        if aa % 1 == 0:
            a = int(aa)
            print(a, b)
            break
        if x + b ** 5 < 0:
            break
        b -= 1



### FIXED CODE ###

#!/usr/bin/env python3

import math
x = int(input())

#aもbも0以上のとき
border = 1;
while border ** 5 - (border - 1) ** 5 < x:
    border += 1

for i in range(border + 1):
    aa = ((x + i ** 5) ** (1.0 / 5.0)) #仮
    a = round(aa)
    if a ** 5 - i ** 5 == x:
        b = i
        print(a, b)
        break
else:
    b = -1

    while x + b ** 5 >= 0:

        aa = ((x + b ** 5) ** (1.0 / 5.0))  # 仮
        a = round(aa)
        if a ** 5 - b ** 5 == x:
            print(a, b)
            break
        b -= 1
from collections import deque 
#from copy import copy
#初期入力
X,Y,A,B,C = (int(x) for x in input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))


# ソート⇒無色と比較
p.sort()
q.sort()
r.sort()

p_dq =deque(p[A-X:])
q_dq =deque(q[B-Y:])
ans_sum =sum(p[A-X:]) + sum(q[B-Y:])
p_change =p_dq.popleft()
q_change =q_dq.popleft()
count_p =0
count_q =0
for i in r:
    if p_change < q_change:
        if i > p_change and count_p < X:
            count_p +=1
            ans_sum = ans_sum -p_change +i
            p_change =p_dq.popleft()

    elif p_change > q_change and count_q < Y:
        if i > q_change:
            count_q +=1
            ans_sum = ans_sum -q_change +i
            q_change =q_dq.popleft()
print(ans_sum)

### FIXED CODE ###

#heapq p,qの最小値側にrの最大値入れていく。
import heapq 

#初期入力
X,Y,A,B,C = (int(x) for x in input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))


# ソート⇒無色と比較
p.sort()
q.sort()
r.sort(reverse=True)

ans_sum =sum(p[-X:]) + sum(q[-Y:])
p_hq = p[-X:]
q_hq = q[-Y:]
heapq.heapify(p_hq)
heapq.heapify(q_hq)
p_change =heapq.heappop(p_hq)
q_change =heapq.heappop(q_hq)
count_p =0
count_q =0
for i in r: #rは大きい順
    if p_change <= q_change and p_change < i:
        if  count_p < X:
            heapq.heappush(p_hq,i)
            count_p +=1
            ans_sum = ans_sum -p_change +i
            p_change =heapq.heappop(p_hq)
    elif p_change > q_change and q_change < i:
        if  count_q < Y:
            heapq.heappush(q_hq,i)
            count_q +=1
            ans_sum = ans_sum -q_change +i
            q_change =heapq.heappop(q_hq)
print(ans_sum)
INF=1000000000
def getans(i):
    if i>=(n-1):
        dp[n-1]= 0
        return dp[n-1]
    if dp[i]!=-1:
        return dp[i]
    if i==(n-2):
        dp[i]=abs(h[i]-h[i+1])
        return dp[i]
    else:
        dp[i]=min(h[i]-h[i+1]+getans(i+1),h[i]-h[i+2]+getans(i+2))
        return dp[i]


n=int(input())
dp=[-1]*n
h=list(map(int,input().split()))
ans=getans(0)
print(ans)

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
dp=[10**9]*n
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(n-1):
    dp[i+1]=min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
    if i+2<n:
        dp[i+2]=min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
print(dp[-1])
if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    a.sort()

    dp = [True]*int(1e6)

    for i in a:
        if i*2 > len(dp):
            pass
        if dp[i*2-1]==False:
            pass
        else:
            for j in range(2*i-1, len(dp), i):
                dp[j] = False


    count = 0
    for i in set(a):
        if len(set(a))==1:
            break
        if dp[i-1]==True:
            count += 1

    print(count)

### FIXED CODE ###

if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    #s_a.sort()

    dub_a = [0]*(max(s_a)+1)

    for i in l_a:
        dub_a[i] += 1

    dp = [1]*(max(s_a)+1)

    for i in s_a:
        for j in range(2*i, len(dp), i):
            dp[j] = 0


    count = 0
    for i in s_a:
        if dp[i]==1 and dub_a[i]==1:
            count += 1
    print(count)
N = int(input())

if N == 1:
  	print("Heloo World")
  
else:
  	A = int(input())
  	B = int(input())
  print(A + B)

### FIXED CODE ###

n = int(input())

if n == 1:
  print("Hello World")
  
else:
  a = int(input())
  b = int(input())
  print(a + b)
n,*a=map(int,open(0).read().split())
print(q)
ans=0
for t in range(2,n):
    for s in range(n):
        try:
            if s+t>n:
                break
   #         print(q[s:s+t])
            if sum(q[s:s+t])==0:
                ans+=1
        except:
            break
print(ans)

### FIXED CODE ###

from itertools import*
from collections import*
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


n,*a=map(int,open(0).read().split())
print(sum(cmb(v,2)for k,v in Counter(accumulate(a)).items() if v>1)+list(accumulate(a)).count(0))
n = int(input())
s = str(input())
a = 0
for i in range(0,n):
  if s[i] == "A":
    if s[i+1] == "B":
      if s[i+2] == "C":
        a +=1

print(a)

### FIXED CODE ###

n = int(input())
s = str(input())
a = 0
for i in range(0,n-2):
  if s[i] == "A":
    if s[i+1] == "B":
      if s[i+2] == "C":
        a +=1

print(a)
w = int(input())
n = int(input())
nums = list(range(w + 1))
for i in range(n):
    s = list(map(int, input().split(", ")))
    nums[s[0]], nums[s[1]] = nums[s[1]], nums[s[0]]
for j in range(w):
    print(nums[j + 1])

### FIXED CODE ###

w = int(input())
nums = list(range(w + 1))
for _ in range(int(input())):
    a, b = map(int, input().split(","))
    nums[a], nums[b] = nums[b], nums[a]
for x in nums[1:]:
    print(x)
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n, k = map(int, input().strip().split())
  lp = list(map(lambda c:int(c)-1, input().strip().split()))
  lc = list(map(int, input().strip().split()))
  used = [0] * n
  loops = []
  for i in range(n):
    if used[i] == 1:
      continue
      
    ic = i
    loop = []
    while True:
      loop.append(lc[ic])
      used[ic] = 1      
      ic = lp[ic]
      if used[ic] == 1:
        break
    if len(loop) > 0:
      loops.append(loop)
    
    
  def f(loop, k):
    if max(loop) < 0:
      return max(loop)
    
    score = 0
    if sum(loop) > 0:
      score += (k // len(loop)) * sum(loop)
      k = k % len(loop)
    k = min(k, len(loop)-1)
    loop = 2 * loop
    score += max([sum(loop[i:i+ik]) for i in range(len(loop)//2) for ik in range(1, k+1)])
    return score
  
  print(max([f(loop, k) for loop in loops]))

if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-


def main():
  n, k = map(int, input().strip().split())
  lp = list(map(lambda p:int(p)-1, input().strip().split()))
  lc = list(map(int, input().strip().split()))

  used = [0] * n
  loops = []
  for i in range(n):
    if used[i] == 1:
      continue
      
    ic = i
    loop = []
    while used[ic] == 0:
      loop.append(lc[ic])
      used[ic] = 1      
      ic = lp[ic]
      
    if len(loop) > 0:
      loops.append(loop)
    
  def loop_score(loop, k):
    return (k // len(loop)) * sum(loop)
  
  def path_score(loop, k):
    score = 0
    for i in range(len(loop)):
      cumsum = 0
      for j in range(k):
        cumsum += loop[(i+j) % len(loop)]
        score = max(score, cumsum)
    return score
  
  def calc_score(loop, k):
    if max(loop) < 0:
      return max(loop)
    
    if k < len(loop):
      return path_score(loop, k)
    if k >= len(loop):
      k -= len(loop)
      score = 0
      if sum(loop) > 0:
        score += loop_score(loop, k)
      k %= len(loop)
      k += len(loop)
      score += path_score(loop, k)

    return score
  
  print(max([calc_score(loop, k) for loop in loops]))

if __name__=='__main__':
  main()
N=int(input())
def sq(n):
    c=0
    A=[0 for j in range(n**2)]
    for i in range(n//2):
        for j in range(i**2,(i+1)**2):
            A[j]=i
    return A
A=sq(N)[0:N+1]
for n in range(1,N+1):
    c=0
    for x in range(1,A[n]):
        for y in range(1,A[n-x**2]):
            for z in range(1,A[n-x**2-y**2]):
                if n==x**2+y**2+z**2+x*y+y*z+z*x:
                    c=c+1
    print(c)

### FIXED CODE ###

N=int(input())
def sq(n):
    c=0
    A=[0 for j in range(n+1)]
    for i in range(n//2):
        p=(i+1)**2
        if p>n:
            for j in range(i**2,n+1):
                A[j]=i
            break
        else:
            for j in range(i**2,p):
                A[j]=i
    return A
A=sq(N)
a=A[N]
L=[0 for j in range(N+1)]
for x in range(1,a+1):
    for y in range(1,a+1):
        for z in range(1,a+1):
            p=x**2+y**2+z**2+x*y+y*z+z*x
            if p<=N:
                L[p]=L[p]+1
            else:
                break
for i in range(1,N+1):
    print(L[i])
n,W=list(map(int,input().split()))

dp=np.zeros([n+1,W+1],dtype=int)

for i in range(1,n+1):
    w,v=list(map(int,input().split()))
    dp[i]=dp[i-1]
    dp[i][w:]=np.maximum(dp[i-1][:W-w+1]+v,dp[i-1][w:])
print(np.max(dp))

### FIXED CODE ###

import numpy as np

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

dp=np.zeros([n+1,W+1],dtype=int)

for i in range(1,n+1):
    w,v=list(map(int,input().split()))
    dp[i]=dp[i-1]
    dp[i][w:]=np.maximum(dp[i-1][:W-w+1]+v,dp[i-1][w:])
print(np.max(dp))