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

import sys

f_i = sys.stdin

n, q = map(int, f_i.readline().split())

S = [[i] for i in range(n)]

def unite(sets, v1, v2):
    s1 = None
    s2 = None
    for s in sets:
        if v1 in s and v2 in s:
            return None
        elif v1 in s:
            s1 = s
        elif v2 in s:
            s2 = s
        if s1 and s2:
            break
    sets.append(s1 + s2)
    sets.remove(s1)
    sets.remove(s2)

def same(sets, v1, v2):
    for s in sets:
        if v1 in s and v2 in s:
            print(1)
            break
        elif v1 in s or v2 in s:
            print(0)
            break

for l in f_i:
    com, x, y = map(int, l.split())
    if com == 0:
        unite(S, x, y)
    else:
        same(S, x, y)

### FIXED CODE ###

import sys
 
f_i = sys.stdin
 
n, q = map(int, f_i.readline().split())

class DisjointSets:
    def __init__(self, size):
        # negative values are roots(representatives of each tree)
        # positive values represent the parent element
        self.table = [-1 for _ in range(size)]

    def _find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self, x, y):
        s1 = self._find(x)
        s2 = self._find(y)
        if s1 != s2:
            if self.table[s1] < self.table[s2]: # the smaller has more elements
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2

    def isSameSet(self, x, y):
        if self._find(x) == self._find(y):
            print(1)
        else:
            print(0)

S = DisjointSets(n)

for l in f_i:
    com, x, y = map(int, l.split())
    if com == 0:
        S.union(x, y)
    else:
        S.isSameSet(x, y)
### BUGGY CODE ###

N = int(input())
S = input()
# 等間隔でなく3つとも異なる文字である組み合わせ数
Ir, Ig, Ib = [], [], []
Sr = Sg = Sb = 0
for i, c in enumerate(S):
    if c == 'R':
        Ir.append(i)
        Sr += 1
    elif c == 'G':
        Ig.append(i)
        Sg += 1
    else:
        Ib.append(i)
        Sb += 1
A = Sr * Sg * Sb
for ir in Ir:
    for ig in Ig:
        if 2*ig-ir in Ib:
            A -= 1
        if 2*ir-ig in Ib:
            A -= 1
        irg = ir+ig
        if irg%2 == 0 and irg//2 in Ib:
            A -= 1
print(A)


### FIXED CODE ###

N = int(input())
S = input()
Sr = Sg = Sb = 0
for c in S:
    if c == 'R':
        Sr += 1
    elif c == 'G':
        Sg += 1
    else:
        Sb += 1
A = Sr * Sg * Sb
for sep in range(1,(N+1)//2):
    for i in range(N-2*sep):
        if S[i] != S[i+sep] and S[i+sep] != S[i+2*sep] and S[i] != S[i+2*sep]:
            A -= 1
print(A)
### BUGGY CODE ###

N = int(input())
S = str(input())
ans = 0

for j in range(1, N+1):
    if S[-j] == '#':
        j += 1
    else:
        break

if j == 1:
    last = 0
else:
    last = j-1
i = 0
while i < N:
    if S[i:i+2] == '#.':
        ans += 1
        S = S[:i+1] + '#' + S[i+2:]
    i += 1

print(min(ans, N-ans-last))


### FIXED CODE ###

N = int(input())
S = str(input())

ans = [S.count('.')]
for i in range(N):
    temp = ans[-1]
    if S[i] == '#':
        temp += 1
    else:
        temp -= 1
    ans.append(temp)
    
print(min(ans))
### BUGGY CODE ###

import sys
s=input()
A,B =map(int,input().split())
t = 0
k=0
L=len(s)
table=[[] for i in range(2)]
for i in range(len(s)):
    if s[i]=='F':
        k+=1
    else:
        table[t].append(k)
        t=(t+1)%2
        k=0
table[t].append(k)
Lx=set()
Lx.add(table[0][0])
for i in range(1,len(table[0])):
    x=table[0][i]
    T=set()
    for a in Lx:
        if -L<=a+x<=L:
            T.add(a+x)
        if -L<=a-x<=L:
            T.add(a-x) 
    Lx=T
flag=True
for a in Lx:
    if a==A:
        flag =False
if flag:
    print('No')
    sys.exit()

Lx=set()
Lx.add(0)
for i in range(len(table[1])):
    x=table[1][i]
    T=set()
    for a in Lx:
        if -L<=a+x<=L:
            T.add(a+x)
        if -L<=a-x<=L:
            T.add(a-x) 
    Lx=T
flag=True
for a in Lx:
    if a==B:
        flag =False
if flag:
    print('No')
    sys.exit()
print('Yes')

### FIXED CODE ###

import sys
s=input()
A,B =map(int,input().split())
table=[[] for i in range(2)]#0が横1が縦
t = 0
k=0
for i in range(len(s)):
    if s[i]=='F':
        k+=1
    else:
        table[t].append(k)
        t=(t+1)%2
        k=0
table[t].append(k)
L=len(s)
Lx=[set() for i in range(len(table[0]) +1)]
Ly=[set() for i in range(len(table[1]) +1)]
Lx[0].add(0)
Ly[0].add(0)
for i in range(len(table[0])):
    x = table[0][i]
    if i==0:
        Lx[1].add(x)
        continue
    for a in Lx[i]:
        if -L<=a+x<=L:
            Lx[i+1].add(a+x)
        if -L<=a-x<=L:
            Lx[i+1].add(a-x) 
flag=True
for a in Lx[len(table[0])]:
    if a==A:
        flag =False
if flag:
    print('No')
    sys.exit()
    
for i in range(len(table[1])):
    x = table[1][i]
    for a in Ly[i]:
        if -L<=a+x<=L:
            Ly[i+1].add(a+x)
        if -L<=a-x<=L:
            Ly[i+1].add(a-x)
flag=True
for a in Ly[len(table[1])]:
    if a==B:
        flag =False
if flag:
    print('No')
    sys.exit()
    
print('Yes')
### BUGGY CODE ###

n=int(input())
p=list(map(int,input().split()))
cnt =0
for i in range(n):
    flg = True
    for j in range(i):
        if p[i] > p[j]:
            flg = False
            break
    if flg:
        cnt += 1
print(cnt)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
cnt =0
mi=n + 1
for i in range(1,n+1):
    mi = min(mi,p[~-i])
    if mi == p[i-1]:
        cnt+=1

print(cnt)
### BUGGY CODE ###

def get_subordinate(n, members):
    for i in range(1, n+1):
        count = 0
        for member in members:
            if i == member:
                count += 1
        print(count)


if __name__ == '__main__':
    n = int(input())
    members = list(map(int, input().rstrip().split()))
    get_subordinate(n, members)



### FIXED CODE ###

def get_subordinate(n, members):
    new_dict = {}

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

    for member in members:
        if member in new_dict:
            new_dict[member] += 1

    print(*new_dict.values(), sep="\n")


if __name__ == '__main__':
    n = int(input())
    members = list(map(int, input().rstrip().split()))
    get_subordinate(n, members)
### BUGGY CODE ###

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

for i in range(k):
    if a > 0:
        a -= 1
    else:
        b -= 1

print(a,b)

### FIXED CODE ###


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

if a + b <= k:
    print(0,0)
else:
    if a >=  k:
        print(a-k,b)
    else:
        print(0,b-(k-a))
### BUGGY CODE ###

N = int(input())
s = [[' '.join(sorted(i)) for i in input().split()] for _ in range(N)]
count = 0
for i in range(len(s)):
  for j in range(i+1, len(s)):
    if s[i][0] == s[j][0]:
      count += 1
print(count)

### FIXED CODE ###

dict={}
for _ in range(int(input())):
  s=''.join(sorted(input()))
  if s not in dict: dict[s]=1
  else: dict[s]+=1
print(sum([i*(i-1)//2 for i in dict.values()]))
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
import sys


def main():
    input = sys.stdin.readline

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

    def check(x):
        # k番目の数がx以下であるか
        # x以下の数字がk個以上あるか
        cnt = 0
        for i, ai in enumerate(a):
            if ai > 0:
                idx = bisect_right(a, x // ai)
                cnt += max(idx - i - 1, 0)
            elif ai < 0:
                idx = bisect_left(a, -(x // abs(ai)))
                # cnt += n - idx
                cnt += n - max(idx, i + 1)
            else:
                # ai == 0
                if x >= 0:
                    cnt += n - i - 1

            if cnt >= k:
                return True
        # print('check', x, cnt)
        return cnt >= k

    # lb = -10**18  # False
    # ub = +10**18  # True
    lb = min(a[0]**2, a[0] * a[-1], a[-1]**2) - 1  # False
    ub = max(a[0]**2, a[0] * a[-1], a[-1]**2) + 1  # True

    while ub - lb > 1:
        mid = (ub + lb) // 2
        # print(lb, ub)
        if check(mid):
            ub = mid
        else:
            lb = mid

    print(ub)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

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

a_minus = a_zero = a_plus = 0
for i in range(n):
    if a[i] > 0:
        a_plus += 1
    elif a[i] == 0:
        a_zero += 1
    else:
        a_minus += 1

aa_minus = a_minus * a_plus
aa_zero = a_zero * (n - a_zero) + a_zero * (a_zero - 1) // 2


def check_minus(x):
    # k番目の数がx(<0)以下であるか
    # x以下の数字がk個以上あるか
    cnt = 0
    j = a_minus + a_zero
    for i in range(a_minus):
        # a[i] < 0
        while j < n and a[i] * a[j] > x:
            j += 1
        cnt += n - j

    return cnt >= k


def check_plus(x):
    # k番目の数がx(>0)以下であるか
    # x以下の数字がk個以上あるか

    def func(b, m):
        # 昇順ソート済みの数列b (長さm)
        # 掛け算してx以下となる数を求める
        c = 0
        j = m - 1
        for i in range(m):
            while j > 0 and b[i] * b[j] > x:
                j -= 1
            c += max(j - i, 0)
        return c

    cnt = aa_minus + aa_zero
    cnt += func(a[-a_plus:], a_plus)
    cnt += func(list(reversed(a[:a_minus])), a_minus)
    return cnt >= k


if k <= aa_minus:
    # k番目の数は負の数
    lb = a[0] * a[-1] - 1  # False
    ub = 0  # True
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check_minus(mid):
            ub = mid
        else:
            lb = mid

    ans = ub
elif k <= aa_minus + aa_zero:
    # k番目の数は0
    ans = 0
else:
    # k番目の数はプラス
    lb = 0  # False
    ub = max(a[0]**2, a[-1]**2) + 1  # True
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check_plus(mid):
            ub = mid
        else:
            lb = mid

    ans = ub

print(ans)
### BUGGY CODE ###

import itertools

n = int(input())
a = list(input().split())
ans = 0
mod = 1000000007
for v in itertools.combinations(a,2):
    ans += int(v[0])*int(v[1])
print(ans%mod)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
mod = 1000000007
s = [0]*(n+1)
for i in range(n):
    s[i+1] = s[i] + a[i]
for i in range(n):
    ans += a[i]*(s[n]-s[i+1])
print(ans%mod)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    import numpy as np
    from collections import Counter

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

    tmp = np.array(list(c.values()))
    l1= tmp*(tmp-1)//2
    l2= (tmp-1)*((tmp-1)-1)//2
    S = np.sum(l1)

    for a in A:
        r = list(c).index(a)
        sum = S + l2[r] -l1[r]
        print(int(sum))
        
if __name__ == '__main__':
    main()


### FIXED CODE ###

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

import collections 
c=collections.Counter(A)
sum=0
for i in c:
  sum+=c[i]*(c[i]-1)//2  
for a in A:
  print(sum - c[a]*(c[a]-1)//2 + (c[a]-1)*(c[a]-2)//2)
### BUGGY CODE ###

r, c = map(int, input().split())

cc = [input() for i in range(r)]

from collections import deque


# 縦がｙ 横がx　だから座標はy,xて書く
st=[]
for i in range(r):
    for j in range(c):
        if cc[i][j]=="#":
            st.append([i,j])

# 保留スタックtodoにスタートの位置情報を入れる
todo=deque(st)
# 検知済みリストseenを-1で初期化 (何も検知してないてこと)
seen=[[-1 for i in range(c)] for j in range(r)]

# seenにはどんだけの手数でそこに到達できるかを入れる
# 例えばスタート地点は手数0でいけるから0を入れる
for i in range(len(st)):
    seen[st[i][0]][st[i][1]]=0

# 4方向の移動リスト これ使って移動していく
ido=[[1,0],[0,1],[-1,0],[0,-1]]
m=0
# 保留リストtodoが空になるまでやる
while todo:
    y, x=todo.popleft() # 現在地は保留からの先頭とりだす
    for i in range(4): # 現在地から4方向を見る
        ny, nx=y+ido[i][0], x+ido[i][1] # 現在地から隣の座標
        # 隣の座標が区画をはみ出さないかつ、検知してないときに
        if 0<=ny<r and 0<=nx<c and seen[ny][nx]==-1 and cc[ny][nx]!="#":
            # 隣に行けるということなので検知してその手数を格納
            seen[ny][nx]=seen[y][x]+1 # 手数＝前の地点の手数+1
            todo.append([ny,nx]) # 保留リストにも入れとく
            if seen[ny][nx]>=m:
                m=seen[ny][nx]
       

print(m)

### FIXED CODE ###

r, c = map(int, input().split())

cc = [input() for i in range(r)]

from collections import deque


# 縦がｙ 横がx　だから座標はy,xて書く
st=[]
for i in range(r):
    for j in range(c):
        if cc[i][j]=="#":
            st.append([i,j])

# 保留スタックtodoにスタートの位置情報を入れる
todo=deque(st)
# 検知済みリストseenを-1で初期化 (何も検知してないてこと)
seen=[[-1 for i in range(c)] for j in range(r)]

# seenにはどんだけの手数でそこに到達できるかを入れる
# 例えばスタート地点は手数0でいけるから0を入れる
for i in range(len(st)):
    seen[st[i][0]][st[i][1]]=0

# 4方向の移動リスト これ使って移動していく
ido=[[1,0],[0,1],[-1,0],[0,-1]]
m=0
# 保留リストtodoが空になるまでやる
while todo:
    y, x=todo.popleft() # 現在地は保留からの先頭とりだす
    for i in range(4): # 現在地から4方向を見る
        ny, nx=y+ido[i][0], x+ido[i][1] # 現在地から隣の座標
        # 隣の座標が区画をはみ出さないかつ、検知してないときに
        if 0<=ny<r and 0<=nx<c and seen[ny][nx]==-1 and cc[ny][nx]!="#":
            # 隣に行けるということなので検知してその手数を格納
            seen[ny][nx]=seen[y][x]+1 # 手数＝前の地点の手数+1
            todo.append([ny,nx]) # 保留リストにも入れとく
            if seen[ny][nx]>=m:
                m=seen[ny][nx]
       

print(m)
### BUGGY CODE ###

N = int(input())
cnt = 0
for A in range(1,N+1):
    for B in range(1,N//A+1):
        C = N-A*B
        if C>0:
            cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
cnt = 0
for A in range(1,N+1):
    for B in range(1,N//A+1):
        C = N-A*B
        if C>0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

import collections
n = int(input())
ls = [input() for i in range(n)]
c = collections.Counter(ls)
a = c.most_common()[0][1]
b = []
for j in range(len(c.most_common())):
    if c.most_common()[j][1] == a:
        b.append(c.most_common()[j][0])
b.sort()
for k in range(len(b)):
    print(b[k])

### FIXED CODE ###

import collections
n = int(input())
ls = [input() for i in range(n)]
c = collections.Counter(ls)
mx = max(c.values())
A = [e for e,j in c.items() if j == mx]
A.sort()
for p in A:
  print(p)
### BUGGY CODE ###

# coding: utf-8

from copy import deepcopy

import sys
sys.setrecursionlimit(100000)

N, X, Y = map(int, input().split())

# from time import time
# start = time()

# neighbor = {}
# for i in range(1, N):
#     neighbor[i] = [i+1]
# for i in range(X+4, Y):
#     neighbor[i] = [i-1, i+1]
# neighbor[X] = [X+1, Y]
# neighbor[Y] = [Y-1, Y+1]
# neighbor[N] = [] if Y < N else [N-1] 
# print(neighbor)

neighbor = {}
for i in range(1, X):
    neighbor[i] = [i+1]
for i in range(Y+1, N):
    neighbor[i] = [i+1]
for i in range(X+1, Y):
    neighbor[i] = [i-1, i+1]
neighbor[X] = [X+1, Y]
neighbor[Y] = [Y-1, Y+1]
neighbor[N] = [] if Y < N else [N-1]
# print(neighbor)

# print(neighbor)

# neighbor = {i: [i-1, i+1] for i in range(2, N)}
# neighbor[1] = [2]
# neighbor[N] = [N-1]
# neighbor[X].append(Y)
# neighbor[Y].append(X)

# appeared_st = set([])
appeared_st = [set([]) for _ in range(N+1)]
# appeared_st[0] = 0
n_k = [0] * N
s_t_dist_dict = {}


# def rec(n, dist, s, k, appeared):
#     # print(appeared_st)
#     if dist == k:
#         # if k == 2:
#         #     input()
#         if s < n and n not in appeared_st[s]:
#             appeared_st[s].add(n)
#             appeared_st[0] += 1
#             # print(appeared_st)

#     toes = [node for node in neighbor[n] if node not in appeared]
#     for to in toes:
#         appeared_copy = deepcopy(appeared)
#         appeared_copy.add(to)
#         rec(to, dist+1, s, k, appeared_copy)


def rec(n, dist, s, limit, appeared, X, Y):
    if s < n:
        ke = "{}.{}".format(s, n)
        if ke in s_t_dist_dict:
            if dist < s_t_dist_dict[ke]:
                n_k[s_t_dist_dict[ke]] -= 1
                s_t_dist_dict[ke] = dist
                n_k[dist] += 1
        else:
            s_t_dist_dict[ke] = dist
            n_k[dist] += 1
            
    # if s < n and n not in appeared_st[s]:
    #     appeared_st[s].add(n)
    #     n_k[dist] += 1
    #     print(appeared_st)
    #     print(n_k)
    #     input()

    if dist == limit:
        return None
    
    if X < n < Y and n - X + 1 > limit - dist:
        return None

    toes = [node for node in neighbor[n] if node not in appeared]
    for to in toes:
        appeared_copy = deepcopy(appeared)
        appeared_copy.add(to)
        rec(to, dist+1, s, limit, appeared_copy, X, Y)


for s in range(1, N):
    rec(s, 0, s, N-1, {s}, X, Y)

for k in range(1, N):
    print(n_k[k])

# for k in range(1, N):
#     tmp = appeared_st[0]

#     for s in range(1, N+1):
#         rec(s, 0, s, k, {s})

    # print(appeared_st[0] - tmp)

# print(appeared_st)
# print(len(appeared_st))
            
# print(time() - start)


### FIXED CODE ###

# coding: utf-8

N, X, Y = map(int, input().split())

n_k = [0] * (N+1)

for i in range(1, N):
    for j in range(i+1, N+1):
        n_k[min(abs(j-i), abs(X-i) + 1 + abs(j-Y))] += 1

for k in range(1, N):
    print(n_k[k])
### BUGGY CODE ###

mod = 10**9+7
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)

if len(a) != len(set(a)) or len(b) != len(set(b)):
    print(0)
    exit()

c = 1
N = 0
M = 0
for k in range(n*m, 0, -1):
    if k in a and k in b:
        N += 1
        M += 1
    elif k in a:
        c *= M
        N += 1
    elif k in b:
        c *= N
        M += 1
    else:
        c *= M*N - (m*n-k)
    c %= mod

print(c)


### FIXED CODE ###

mod = 10**9+7
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)

if len(a) != len(set(a)) or len(b) != len(set(b)):
    print(0)
    exit()

a = set(a)
b = set(b)

c = 1
N = 0
M = 0
for k in range(n*m, 0, -1):
    if k in a and k in b:
        N += 1
        M += 1
    elif k in a:
        c *= M
        N += 1
    elif k in b:
        c *= N
        M += 1
    else:
        c *= M*N - (m*n-k)
    c %= mod

print(c)
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split(' ')))
B1 = defaultdict(int)
B0 = defaultdict(int)
for x in A:
    bA = format(x,"b").zfill(60)
    for i in range(60):
        if bA[i] == "1":
            B1[i] += 1
        elif bA[i] == "0":
            B0[i] += 1
ans = 0
for i in range(60):
    ans = (ans + 2**(59-i)*B1[i]*B0[i]) % (10**9+7)
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split(' ')))
B1 = [0 for i in range(60)]
B0 = [0 for i in range(60)]
for x in A:
    bA = format(x,"b").zfill(60)
    for i in range(60):
        if bA[i] == "1":
            B1[i] += 1
        elif bA[i] == "0":
            B0[i] += 1
ans = 0
for i in range(60):
    ans = (ans + 2**(59-i)*B1[i]*B0[i]) % (10**9+7)
print(ans)
### BUGGY CODE ###

def chn(c):
	tot=1
	for i in range(len(c)):
		if c[i]==0:
			return 0
		
		tot=tot*c[i]
		
	if tot>pow(10,18):
		return -1
	return tot


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

print(chn(c))


### FIXED CODE ###

n=int(input())
c=sorted(list(map(int,input().split())))[::-1]
if c[-1]==0:
	print(0)
else:
	tot=1
	flag=0
	for i in range(len(c)):
		tot*=c[i]
		if tot>1000000000000000000:
			print(-1)
			flag=1
			break
	if flag==0:
		print(tot)
### BUGGY CODE ###

N = int(input())
p_list  = list(map(int,input().strip().split(" ")))

c = 1
if p_list == sorted(p_list):
    print(1)
    #print("if")
elif p_list == sorted(p_list, reverse=True):
    print(len(p_list))
    #print("elif")
else:
    for i in range(N):
        temp = 0
        for j in range(i):
            if p_list[i] <= p_list[j]:
                temp += 1
                if temp == i:
                    c += 1
            else:
                break
    print(c)
    #print("else")

### FIXED CODE ###

N = int(input())
p_list  = list(map(int,input().strip().split(" ")))

ans = 1
mi = p_list[0]

for i in range(1, N):
    if mi >= p_list[i]:
        ans += 1
        mi = p_list[i]
        
print(ans)
### BUGGY CODE ###

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

ans_list = []
for i in range(N):
    print((A_list.index(i + 1) + 1), end = ' ')

### FIXED CODE ###

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

ans_list = [0] * N

for index, i in enumerate(A_list):
    ans_list[i - 1] = index + 1

print(' '.join(map(str, ans_list)))
### BUGGY CODE ###

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


def main():
    n, m = map(int, input().split())
    ac = []
    wa = []
    wa_count = 0
    for i in range(m):
        p, s = input().split()
        if p in ac:
            continue
        else:
            if s == 'AC':
                ac.append(p)
                wa_count += wa.count(p)
            else:
                wa.append(p)
    print(len(ac), wa_count)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import numpy as np


def main():
    N, M = map(int, input().split())

    AC = np.array([0] * N)
    WA = np.array([0] * N)

    for i in range(M):
        p, S = input().split()

        if AC[int(p) - 1] == 0 and S == 'WA':
            WA[int(p) - 1] += 1
        else:
            AC[int(p) - 1] = 1
    print(sum(AC), sum(AC * WA))


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

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,k=nii()
p=lnii()
c=lnii()

ans=-10**18
for i in range(n):
  ini_x=i
  x=i
  point=[]

  t_ans=0
  cnt=0
  t_max=-10**18
  while True:
    x=p[x]-1
    t_point=c[x]
    point.append(t_point)
    t_ans+=t_point
    t_max=max(t_max,t_ans)
    cnt+=1
    if x==ini_x:
      break

  if t_ans<0:
    ans=max(ans,t_max)
  else:
    num=k//cnt
    num-=1
    c_ans=t_ans*num
    c_max=c_ans
    zan=k-(num*cnt)
    for j in range(zan):
      x=p[x]-1
      c_ans+=c[x]
      c_max=max(c_max,c_ans)
    ans=max(ans,c_max)

print(ans)

### FIXED CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,k=nii()
p=lnii()
c=lnii()

ans=-10**18
for i in range(n):
  ini_x=i
  x=i
  point=[]

  t_ans=0
  cnt=0
  t_max=-10**18
  while True:
    x=p[x]-1
    t_point=c[x]
    point.append(t_point)
    t_ans+=t_point
    t_max=max(t_max,t_ans)
    cnt+=1
    if x==ini_x:
      break

  if t_ans<0:
    ans=max(ans,t_max)
  else:
    num=k//cnt
    num-=1
    c_ans=t_ans*num
    c_max=c_ans
    zan=k-(num*cnt)
    for j in range(zan):
      x=p[x]-1
      c_ans+=c[x]
      c_max=max(c_max,c_ans)
    ans=max(ans,c_max)

print(ans)
### BUGGY CODE ###

import math


def inputIntList():
    return [int(s) for s in input().split()]


def inputInt():
    return int(input())


def main():
    N, capacity = inputIntList()
    w = [0 for _ in range(N)]
    v = [0 for _ in range(N)]
    for i in range(N):
        w[i], v[i] = inputIntList()

    dp = [[float("inf") for _ in range(N * 1000 + 1)] for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(N * 1000 + 1):
            if j < v[i]:
                dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])
            else:
                dp[i + 1][j] = min(dp[i][j - v[i]] + w[i], dp[i][j])
    ret = 0
    for value, weight in enumerate(dp[N]):
        if weight <= capacity:
            ret = max(ret, value)

    return ret


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

import math


def inputIntList():
    return [int(s) for s in input().split()]


def inputInt():
    return int(input())


def main():
    N, capacity = inputIntList()
    w = [0 for _ in range(N)]
    v = [0 for _ in range(N)]
    for i in range(N):
        w[i], v[i] = inputIntList()

    dp = [[float("inf") for _ in range(N * 1000 + 1)] for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(N * 1000 + 1):
            if j < v[i]:
                dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])
            else:
                dp[i + 1][j] = min(dp[i][j - v[i]] + w[i], dp[i][j])
    ret = 0
    for value, weight in enumerate(dp[N]):
        if weight <= capacity:
            ret = max(ret, value)

    return ret


if __name__ == "__main__":
    print(main())