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

import sys
MOD = 998244353


def main():
    input = sys.stdin.buffer.readline
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[None] * (s + 1) for _ in range(n + 1)]
#     dp[i][j]:=集合{1..i}の空でない部分集合T全てについて,和がjとなる部分集合の個数の和
    for i in range(n + 1):
        for j in range(s + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
                continue
            if j > a[i - 1]:
                dp[i][j] = dp[i - 1][j] * 2 + dp[i - 1][j - a[i - 1]]
            elif j == a[i - 1]:
                dp[i][j] = dp[i - 1][j] * 2 + pow(2, i - 1, MOD)
            else:
                dp[i][j] = dp[i - 1][j] * 2
            dp[i][j] %= MOD
    print(dp[n][s])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
MOD = 998244353


def main():
    input = sys.stdin.buffer.readline
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[None] * (s + 1) for _ in range(n + 1)]
#     dp[i][j]:=集合{1..i}の空でない部分集合T全てについて,和がjとなる部分集合の個数の和
    for i in range(n + 1):
        for j in range(s + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
                continue
            if j > a[i - 1]:
                dp[i][j] = dp[i - 1][j] * 2 + dp[i - 1][j - a[i - 1]]
            elif j == a[i - 1]:
                dp[i][j] = dp[i - 1][j] * 2 + pow(2, i - 1, MOD)
            else:
                dp[i][j] = dp[i - 1][j] * 2
            dp[i][j] %= MOD
    print(dp[n][s])


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

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

# なんこか入力
n,m = map(int, input().split())

# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
b = [0]*(n+1)
bb=0

for i in range(0,n) :
    b[i+1] = bb = ( bb+a[i] ) % m
    
answer = 0
for r in range(1,n+1) :
    for l in range(0,r) :
        if (b[r] - b[l] ) == 0:
            answer += 1

print(answer)



### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

# なんこか入力
n,m = map(int, input().split())

# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
b = [0]*(n)
c ={0:1}
bb=0
for i in range(0,n) :
    bb = ( bb+a[i] ) % m
    c[bb] = c.get(bb,0) + 1
    
    
answer = 0
#print(c)

for i,j in c.items():
    if j > 1:
        answer +=  (j * (j-1) // 2 )

print(answer)
### BUGGY CODE ###


def resolve():

    N=int(input())
    A=list(map(int,input().split()))
    ls=[]
    for i in range(N):
        ls.append((i,A[i]-1))
    cnt=0
    for (s,t) in ls:
        if (t,s) in ls:
            cnt+=1
    print(cnt//2)



resolve()

### FIXED CODE ###

def resolve():

    N=int(input())
    A=list(map(int,input().split()))
    cnt=0
    for i in range(N):
        if A[A[i]-1]==i+1:
            cnt+=1
    print(cnt//2)



resolve()
### BUGGY CODE ###

# coding: utf-8
from functools import lru_cache
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

@lru_cache(maxsize = None)
def f2(i, j):
    if i == j:
        return(a[i])
    r = a[i] - f2(i + 1, j)
    l = a[j] - f2(i, j - 1)
    return(r if r > l else l)

n = int(input()) # 1 <= n <= 3000
a = list(map(int, input().split()))
print(f2(0, n - 1))


### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

def f(n, a):
    dp = [[0] * n for _ in range(n)]
    # dp[i][i] を a[i] で初期化
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        dpi = dp[i]
        dpi1 = dp[i + 1]
        for j in range(i + 1, n):
            r = a[i] - dpi1[j]
            l = a[j] - dpi[j - 1]
            dp[i][j] = r if r > l else l
            # dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    return(dp[0][-1])

n = int(input()) # 1 <= n <= 3000
a = list(map(int, input().split()))
print(f(n, a))
### BUGGY CODE ###

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

INF = int(1e18)
G = np.full((N, N), INF)
for i in range(N):
    G[i][i] = 0

edge = []
for i in range(M):
    a, b, c = [int(i) for i in input().split()]
    a, b = a - 1, b - 1
    G[a][b] = G[b][a] = c
    edge.append((a, b, c))


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

ans = 0
for (a, b, c) in edge:
    flag = False
    for s in range(N):
        for t in range(N):
            flag = flag | (G[s][t] == G[s][a] + c + G[b][t])

    ans = ans + (flag == False)
print(ans)
    
        
    



### FIXED CODE ###

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

INF = int(1e18)
G = np.full((N, N), INF)
for i in range(N):
    G[i][i] = 0

edge = []
for i in range(M):
    a, b, c = [int(i) for i in input().split()]
    a, b = a - 1, b - 1
    G[a][b] = G[b][a] = c
    edge.append((a, b, c))


rng = range(N)
for k in rng:
    for i in rng:
        for j in range(i + 1, N):
            x = G[i][k] + G[k][j]
            if G[i][j] > x:
                G[i][j] = G[j][i] = x;
                
ans = 0
for (a, b, c) in edge:
    ans = ans + (G[a][b] != c)
print(ans)
### BUGGY CODE ###

import sys
from operator import itemgetter

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    n = int(input())
    l = [list(map(int, input().split())) for i in range(n)]

    is_possible = True
    for e in l:
        if sum([i[0] for i in l if i[1] <= e[1]]) > e[1]:
            is_possible = False
            break

    print("Yes" if is_possible else "No")


### FIXED CODE ###

import sys
from operator import itemgetter

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    n = int(input())
    l = [list(map(int, input().split())) for i in range(n)]
    l.sort(key=itemgetter(1))

    is_possible = True
    sum = 0
    for e in l:
        sum += e[0]
        if sum > e[1]:
            is_possible = False
            break

    print("Yes" if is_possible else "No")
### BUGGY CODE ###

from collections import defaultdict, Counter, deque

NA, NB, NM = list(map(int, input().split()))

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

coupons = defaultdict(list)
for i in range(NM):
    x, y, c = list(map(int, input().split()))
    coupons[(x, y)].append(c)

best = float('inf')
for i, a in enumerate(A):
    for j, b in enumerate(B):
        cost = a + b
        if (i + 1, j + 1) in coupons:
            cost -= max(coupons[(i + 1, j + 1)])
        best = min(cost, best)
print(best)

### FIXED CODE ###

from collections import defaultdict, Counter, deque

NA, NB, NM = list(map(int, input().split()))

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


best = min(A) + min(B)

for i in range(NM):
    x, y, c = list(map(int, input().split()))
    best = min(best, A[x - 1] + B[y - 1] - c)


print(best)
### BUGGY CODE ###

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

def get_cd(x1,x2):
    cd=[]
    for i in range(1,min(x1,x2)+1):
        if x1%i==0 and x2%i==0:
            cd.append(i)
    return cd

cd_AB=get_cd(A,B)

for j in range (0,len(cd_AB)-1):
    for k in range(j+1,len(cd_AB)):
            if(len(get_cd(cd_AB[j],cd_AB[k]))>1):
                cd_AB[k]=0

print(len(cd_AB)-cd_AB.count(0))

### FIXED CODE ###

def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        count=0
        while n % b == 0:
            n //= b
            count+=1
            if(count==1):
                fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

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

A,B=map(int,input().split())
g=gcd(A,B)
if(g==1):
    print("1")
else:
    print(len(factorize(g))+1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-


def main():
    from fractions import gcd

    n = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    lcm = 1
    ans = 0

    for ai in a:
        lcm = lcm * ai // gcd(lcm, ai)

    for ai in a:
        ans += lcm // ai

    print(ans % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-


def main():
    from fractions import gcd

    n = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    lcm = 1
    ans = 0

    for ai in a:
        lcm = lcm * ai // gcd(lcm, ai)

    for ai in a:
        ans += lcm // ai

    print(ans % mod)


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

def solve():
  import sys
  import math

  sys.setrecursionlimit(10**7)
  readline=sys.stdin.readline

  n,m = map(int,input().split())
  a = list(map(int,input().split()))
  a.sort()
  
  for i in range(m):
    a += [a.pop()//2]
    a.sort()
  
  print(sum(a))

if __name__ == '__main__':
  solve()

### FIXED CODE ###

def solve():
  import sys
  import math
  import heapq

  sys.setrecursionlimit(10**7)
  readline=sys.stdin.readline

  n,m = map(int,input().split())
  a = [-int(i) for i in input().split()]
  heapq.heapify(a)
  
  t = heapq.heappop(a)
  for i in range(m-1):
    t = heapq.heappushpop(a,t/2)
  heapq.heappush(a,t/2)
  
  print(sum(int(-i) for i in a))

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

import numpy as np

k = int(input())

abc = []
abc = [[a,b,c] for a in range(1,k+1) for b in range(1,k+1) for c in range(1,k+1) ]

answer = 0
for i in range(len(abc)):
    answer += np.gcd.reduce(abc[i])

print(answer)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
 
K = int(read())
 
x = np.arange(1, K + 1)
nums = np.gcd.outer(np.gcd.outer(x, x), x)
print(nums.sum())
### BUGGY CODE ###

a,b,c,k=map(int,input().split())
aa=0
while(k!=0):
    if(a>0):
        aa+=1
        a-=1
        k-=1
        continue
    if(b>0):
        aa+=0
        b-=1
        k-=1
        continue
    if(c>0):
        aa-=1
        c-=1
        k-=1
        continue
    # k-=1
print(aa)        

### FIXED CODE ###

a,b,c,k=map(int,input().split())
aa=0
if(k<=a):
    aa+=k
if(k>a):
    aa+=a
    k=k-a
if(k<=b and k>0):
    k=0
if(k>b):
    k=k-b
if(k<=c and k>0):
    aa=aa-k
if(k>c and k>0):
    aa=aa-c
print(aa)
### BUGGY CODE ###

s = input()
ans = 0
for i in range(len(s)-3):
    for j in range(i+3, len(s)):
        x = int(s[i:j+1])
        if x %2019 == 0:
            ans += 1
print(ans)

### FIXED CODE ###

import collections
S = list(map(int, input()))[::-1]
mod_list = [0 for _ in range(len(S)+1)]
x = 0
d = 0
for i, s in enumerate(S):
    x += s * pow(10, d, 2019)
    d += 1
    mod_list[i] = x%2019
c = collections.Counter(mod_list)
ans = 0
for i in range(2020):
    ans += c[i] * (c[i]-1)//2
print(ans)
### BUGGY CODE ###

a=int(input())
b=1
for i in range(1,a+1):
  b=b*i
if b<1000000000:
  print(b)
else:
  print(b%1000000007)

### FIXED CODE ###

a=int(input())
b=1
for i in range(1,a+1):
  b=b*i
  if b>1000000007:
    b=b%1000000007
if b<1000000000:
  print(b)
else:
  print(b%1000000007)
### BUGGY CODE ###

def main():
	S = input()
	K = int(input())
	sub = set()
	for i in range(len(S)):
		for j in range(i+1, len(S)+1):
			sub.add(S[i:j])
	sub_list = list(sub)
	sub_list.sort()
	ans = sub_list[K-1]
	print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
def main():
	S = input()
	K = int(input())
	sub = defaultdict(set)
	for i in range(len(S)):
		sub[S[i]].add(S[i:len(S)+1])

	alphabet = [chr(ord('a') + i) for i in range(26)]
	ans = set()
	for c in alphabet:
		if c in sub:
			this_list = list(sub[c])
			this_list.sort()
			for e in this_list:
				for i in range(1, len(e)+1):
					ans.add(e[:i])
					if len(ans) == K:
						print(e[:i])
						return


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

import collections
N = int(input())
A = list(map(int,input().split()))
ans = 1
count = 0
if N == 1:
    if A[0] == 0:
        ans = 1
    else:
        print(0)

if N % 2 == 0:
    for i in range(1, int(N/2)+1):
        if A.count(i*2-1) == 2:
            count += 1
        else:
            ans = 0
else:
    if A.count(0) == 1:
        for i in range(1, int(N/2)+1):
            if A.count(i*2) == 2:
                count += 1

            else:
                ans = 0
    else:
        ans = 0
for i in range(count):
    ans *= 2
    ans %= 1000000007
print(ans)


### FIXED CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
A.sort()
A = collections.Counter(A)

ans = 1
count = 0
if N == 1:
    if A[0] == 1:
        ans = 1
    else:
        ans = 0

elif N % 2 == 0:
    for i in range(1, int(N/2)+1):
        if A[i*2-1] == 2:
            count += 1
        else:
            ans = 0
else:
    if A[0] == 1:
        for i in range(1, int(N/2)+1):
            if A[i*2] == 2:
                count += 1

            else:
                ans = 0
    else:
        ans = 0
for i in range(count):
    ans *= 2
    ans %= 1000000007
print(ans)
### BUGGY CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])


### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13

print(dp[len(S)][5])
### BUGGY CODE ###

N = int(input())
B = input()



B_1 = B.count("1")
mod_list_m1 = []
mod_list_p1 = []

mod_m1 = 0
mod_p1 = 0
for i in range(N):
    if B_1 != 1:
        mm1 = (2**(N-i-1)) % (B_1-1)
        mod_list_m1.append(mm1)
        
    mp1 = (2**(N-i-1)) % (B_1+1)
    mod_list_p1.append(mp1)
mod_p1 = int(B,2) % (B_1+1)
if B_1 != 1:
    mod_m1 = int(B,2) % (B_1-1)

def calc_small(n, iter):
    iter += 1
    mod = n % bin(n).count("1")

    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

for i in range(N):
    if B_1 == 1 and int(B[i]) == 1:
        print(0)
        continue
    mod = (mod_m1 - mod_list_m1[i]) % (B_1-1) if int(B[i]) == 1 else (mod_p1 + mod_list_p1[i]) % (B_1+1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))

    




### FIXED CODE ###

N = int(input())
B = input()

B_1 = B.count("1")
mod_p1 = int(B,2) % (B_1+1)
if B_1 != 1:
    mod_m1 = int(B,2) % (B_1-1)

def calc_small(n, iter):
    iter += 1
    mod = n % bin(n).count("1")

    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

for i in range(N):
    if B_1 == 1 and int(B[i]) == 1:
        print(0)
        continue
    mod = (mod_m1 - pow(2,N-i-1,B_1-1)) % (B_1-1) if int(B[i]) == 1 else (mod_p1 + pow(2,N-i-1,B_1+1)) % (B_1+1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))
### BUGGY CODE ###

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

uf = UnionFind(N)

friend = [[False]*N for _ in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)
    friend[a][b] = True
    friend[b][a] = True

block = [[False]*N for _ in range(N)]

for i in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    block[c][d] = True
    block[d][c] = True

res = []
for i in range(N):
    g = uf.members(i)
    cnt = -1
    for x in g:
        if friend[i][x] or block[i][x]:
            continue
        cnt += 1
    res.append(str(cnt))

print(" ".join(res))

### FIXED CODE ###

N, M, K = map(int, input().split())
 
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
 
uf = UnionFind(N)
 
deg = [0]*N
to = [[] for _ in range(N)]
 
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)
    deg[a] += 1
    deg[b] += 1
 
for i in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    to[c].append(d)
    to[d].append(c)
 
res = []

for i in range(N):
    r = uf.size(i)-1-deg[i]
    for u in to[i]:
        if uf.same(i, u):
            r -= 1
    res.append(str(r))

print(" ".join(res))
### BUGGY CODE ###

from collections import deque
n=deque(int(input()) for _ in range(int(input())))
for _ in range(len(n)): m=n.popleft();print(max(n));n.append(m)

### FIXED CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]
max_num = sorted(a, reverse=True)[0]
max_num2 = sorted(a, reverse=True)[1]
[print(max_num) if i!=max_num else print(max_num2) for i in a]
### BUGGY CODE ###

from bisect import bisect_left
N,Q,*L = map(int, open(0).read().split())
A = L[:N]
S = []
M = []
x = 0
y = 0
m = sum(A)
for i in range(N):
  if i%2==0:
    x += A[i]
    S.append(x)
  else:
    y += A[i]
    S.append(y)
for i in range(N):
  M.append(m)
  m -= A[i]

for q in L[N:]:
  i = bisect_left(A,q)
  if 0<i<N and q-A[i-1]<=A[i]-q:
    i = i-1
  if i>=N-1:
    print(S[N-1])
    continue
  l = -1
  r = N
  while l+1<r:
    s = (l+r)//2
    k = N-1-s
    if s<=i:
      l = s
      continue
    x = s-i+1
    if x>k:
      r = s
      continue
    y = k-x
    m = i-y-1
    if m<0:
      l = s
      continue
    if q-A[m]<=A[s]-q:
      r = s
    else:
      l = s
  a = M[r]
  cnt = N-r
  cnt -= r-i-1
  b = i-cnt
  if b>=0:
    a += S[b]
  print(a)

### FIXED CODE ###

from bisect import bisect_left
N,Q,*L = map(int, open(0).read().split())
A = L[:N]
S = []
M = []
x = 0
y = 0
m = sum(A)
for i in range(N):
  if i%2==0:
    x += A[i]
    S.append(x)
  else:
    y += A[i]
    S.append(y)
for i in range(N):
  M.append(m)
  m -= A[i]

for q in L[N:]:
  i = bisect_left(A,q)
  if 0<i<N and q-A[i-1]<=A[i]-q:
    i = i-1
  if i>=N-1:
    print(S[N-1])
    continue
  l = -1
  r = N
  while l+1<r:
    s = (l+r)//2
    k = N-1-s
    if s<=i:
      l = s
      continue
    x = s-i+1
    if x>k:
      r = s
      continue
    y = k-x
    m = i-y-1
    if m<0:
      l = s
      continue
    if q-A[m]<=A[s]-q:
      r = s
    else:
      l = s
  a = M[r]
  cnt = N-r
  cnt -= r-i-1
  b = i-cnt
  if b>=0:
    a += S[b]
  print(a)
### BUGGY CODE ###

n, k = map(int, input().split())
ps = list(map(int, input().split()))
cs = list(map(int, input().split()))
memo = [[0]*(n+1)for _ in range(n+1)]

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

to_do = []
res = -float('inf')
for i in range(1,n+1):
    tmp_dic = {i:(0,0,i)}
    for j in range(1,n+1):
        tmp_idx,tmp_val = ps[memo[i][j-1][0]-1],memo[i][j-1][1]+cs[ps[memo[i][j-1][0]-1]-1]
        memo[i][j] = [tmp_idx,tmp_val]
        res = max(res,tmp_val)
        if tmp_idx not in tmp_dic:
            tmp_dic[tmp_idx] = (j,tmp_val,tmp_idx)
        else:
            if tmp_val > tmp_dic[tmp_idx][1]:
                to_do.append([i,tmp_dic[tmp_idx][0],tmp_dic[tmp_idx][2],tmp_dic[tmp_idx][1],j-tmp_dic[tmp_idx][0],tmp_val-tmp_dic[tmp_idx][1]])
            else:
                break

if k <= n:
    print(res)
else:
    for do in to_do:
        itr = (k - do[1]) // do[4]
        remain = k - do[1] - do[4] * itr
        tmp_res = do[3] + itr * do[5]
        res = max(res,tmp_res)
        now = do[2]
        for i in range(remain):
            now = ps[now-1]
            tmp_res += cs[now-1]
            res = max(res, tmp_res)
    print(res)

### FIXED CODE ###

n, k = map(int, input().split())
ps = list(map(int, input().split()))
cs = list(map(int, input().split()))

to_do = []
res = -float('inf')
for i in range(1,n+1):
    tmp_idx = i
    tmp_val = 0
    tmp_dic = {i:(0,0,i)}
    for j in range(1,min(n+1,k+1)):
        tmp_idx = ps[tmp_idx-1]
        tmp_val += cs[tmp_idx-1]
        res = max(res,tmp_val)
        if tmp_idx not in tmp_dic:
            tmp_dic[tmp_idx] = (j,tmp_val,tmp_idx)
        else:
            if tmp_val > tmp_dic[tmp_idx][1]:
                to_do.append([i,tmp_dic[tmp_idx][0],tmp_dic[tmp_idx][2],tmp_dic[tmp_idx][1],j-tmp_dic[tmp_idx][0],tmp_val-tmp_dic[tmp_idx][1]])
            break

for do in to_do:
    itr = (k - do[1]) // do[4]
    if itr > 0:
        itr -= 1
    remain = k - do[1] - do[4] * itr
    tmp_res = do[3] + itr * do[5]
    res = max(res,tmp_res)
    now = do[2]
    for i in range(remain):
        now = ps[now-1]
        tmp_res += cs[now-1]
        res = max(res, tmp_res)
print(res)