Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03256 (python)

Fixed submission:
'''
https://beta.atcoder.jp/contests/agc027/submissions/3201641
'''
n, m = map(int, input().split())
s = list(input())

deg = [{'A':0, 'B':0} for _ in range(n)]  # deg[0 - (n - 1)][0 - 1] = 0
g = [list() for _ in range(n)]  # g[0 - (n - 1)] = []

for i in range(m):  # クエリを配列に代入
    x, y = map(int, input().split())
    x, y = x - 1, y - 1  # 1-indexed -> 0-indexed
    deg[x][s[y]] += 1  # 頂点 x に隣接する頂点の個数を管理 : A か B かに応じて, その文字のカウントを 1 増やす
    deg[y][s[x]] += 1  # 頂点 y に隣接する頂点の個数を管理 : A か B かに応じて, その文字のカウントを 1 増やす
    g[x].append(y)  # 頂点 x に隣接する頂点のリストに y を追加
    g[y].append(x)  # 頂点 y に隣接する頂点のリストに x を追加

was = [False for _ in range(n)]  # was[j] = True なら 頂点 j は que に追加済み
que = []  # A か B が隣接しないため, 連結リストから除外する頂点

for i in range(n):  # 全頂点をループ
    if deg[i]['A'] == 0 or deg[i]['B'] == 0:  # A か B が隣接しないなら
        que.append(i)  # 除外頂点リスト que に追加
        was[i] = True  #  was[j] = True は, 除外頂点リスト que に追加済を意味する

for q in que:  # A か B が隣接していない, 除外頂点リストの各頂点をループ（ que はループ中に追加されうる）
    for j in g[q]:  # 除外頂点に隣接する頂点をループ
        deg[j][s[q]] -= 1  # "除外頂点に隣接する頂点" に隣接する頂点の個数を管理 : 除外頂点の文字のカウントを減らす
        if deg[j]['A'] == 0 or deg[j]['B'] == 0:  # "除外頂点に隣接する頂点" に A か B が隣接しないなら
            if not was[j]:  # 頂点 j が que に追加済みの頂点でないなら, que に追加する / 追加済みなら, 隣接する頂点の個数管理は, 終了済み
                was[j] = True
                que.append(j)  # 除外頂点リスト que に追加, ループ回数増える

# 除外頂点を取り除いた後に, 頂点が残っていれば, AABB... を作成できる
# 頂点が残っていなければ, つまり, que に全ての頂点が入っていれば, AABB...を作成できない
print('No' if len(que) == n else 'Yes')

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
s = list(input())

g = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  # 1-indexed -> 0-indexed
    g[a].add(b)  # edge
    g[b].add(a)

q = [True for _ in range(n)]
left = n
i = 0
cnt_ok = 0
while left > 0:
    fa, fb = False, False
    for j in g[i]:
        if s[j] == 'A':
            fa = True
        elif s[j] == 'B':
            fb = True
        if fa and fb:
            break
    if fa and fb:
        cnt_ok += 1
        if cnt_ok == left:
            break
    else:
        s[j] = 'X'  # 除外された頂点
        q[i] = False
        left -= 1
        cnt_ok = 0
    i += 1
    if i == n:
        i = 0

print('Yes' if left > 0 else 'No')
Problem p03267 (python)

Fixed submission:
def iin(): return int(input())

l = iin()
stack = []

ans = [[1, 2, 0]]
x = l
while True:
    if x == 1:
        break
    #x > 2を条件に加えた理由: 
    #x = 1 -> 2の操作を*2で済ませると[1, 2, 0], [2, 3, 0], [2, 3, 1] となり、
    #頂点数が21以上になるケースが出るため, x = 1 -> 2は+1で済ませる
    while x % 2 == 0 and x > 2:
        x //= 2
        stack.append('*2')
    if x == 1:
        break
    x -= 1
    stack.append('+1')

last_v_num = 2
x = 1#L, つまりパスの数
while len(stack) > 0:
    op = stack.pop()
#    print(op)
    if op == '+1':
        x += 1#パスの数を増やす
        ans.append([1, last_v_num, x - 1])#頂点1と最後の頂点を直接結ぶ, 辺の重みはパスの数 - 1
    elif op == '*2':
        x *= 2#パスの数を増やす
        for i in range(len(ans)):
            ans[i][2] *= 2#w *= 2して, 既存のパスの重みを2倍にする
        #最後の頂点の後ろに, 新たな頂点を加えて結ぶ, 辺の重みは0と1
        ans.append([last_v_num, last_v_num + 1, 0])
        ans.append([last_v_num, last_v_num + 1, 1])
        last_v_num += 1

N = last_v_num
M = len(ans)
print(N, M)
for u, v, w in ans:
   print(u, v, w)

Buggy submission (verdict: Runtime Error):
l = iin()
stack = []

ans = [[1, 2, 0]]
x = l
while True:
    if x == 1:
        break
    while x % 2 == 0:
        x //= 2
        stack.append('*2')
    if x == 1:
        break
    x -= 1
    stack.append('+1')

last_v_num = 2
x = 1#L, つまりパスの数
while len(stack) > 0:
    op = stack.pop()
#    print(op)
    if op == '+1':
        x += 1#パスの数を増やす
        ans.append([1, last_v_num, x - 1])#頂点1と最後の頂点を直接結ぶ, 辺の重みはパスの数 - 1
    elif op == '*2':
        x *= 2#パスの数を増やす
        for i in range(len(ans)):
            ans[i][2] *= 2#w *= 2して, 既存のパスの重みを2倍にする
        #最後の頂点の後ろに, 新たな頂点を加えて結ぶ, 辺の重みは0と1
        ans.append([last_v_num, last_v_num + 1, 0])
        ans.append([last_v_num, last_v_num + 1, 1])
        last_v_num += 1

N = last_v_num
M = len(ans)
print(N, M)
for u, v, w in ans:
    print(u, v, w)
Problem p03343 (python)

Fixed submission:
# https://atcoder.jp/contests/arc098/submissions/2581691
inf = float('inf')


def calc_max_a(min_a):
    cands = []  # 候補
    seq = 0
    for i, aa in enumerate(a):
        if aa < min_a:
            if seq >= K:
                cands.extend(sorted(a[i - seq:i])[:seq - K + 1])
            seq = 0
        else:
            seq += 1
    if seq >= K:
        cands.extend(sorted(a[- seq:])[:seq - K + 1])

    if len(cands) < Q:
        return -1  # Query回数の操作ができない
    else:
        return sorted(cands)[Q - 1]  # Q回目の操作で取り出す値


N, K, Q = map(int, input().split())
a = tuple(map(int, input().split()))

ans = inf
for min_a in sorted(set(a)):
    max_a = calc_max_a(min_a)
    if max_a < 0: break  # min_a以上の値を最小値にするような操作は存在しない
    ans = min(ans, max_a - min_a)
print(ans)

Buggy submission (verdict: Runtime Error):
# https://atcoder.jp/contests/arc098/submissions/2581691
from math import inf


def calc_max_a(min_a):
    cands = []  # 候補
    seq = 0
    for i, aa in enumerate(a):
        if aa < min_a:
            if seq >= K:
                cands.extend(sorted(a[i - seq:i])[:seq - K + 1])
            seq = 0
        else:
            seq += 1
    if seq >= K:
        cands.extend(sorted(a[- seq:])[:seq - K + 1])

    if len(cands) < Q:
        return -1  # Query回数の操作ができない
    else:
        return sorted(cands)[Q - 1]  # Q回目の操作で取り出す値


N, K, Q = map(int, input().split())
a = tuple(map(int, input().split()))

ans = inf
for min_a in sorted(set(a)):
    max_a = calc_max_a(min_a)
    if max_a < 0: break  # min_a以上の値を最小値にするような操作は存在しない
    ans = min(ans, max_a - min_a)
print(ans)
Problem p03353 (python)

Fixed submission:
def f(myC, s, chrs, lst, k):
    if len(lst) == k:
        print(lst[k - 1])
        exit()
    else:
        for c in chrs:
            buf = myC + c
            if buf in s:
                lst += [buf]
                ##print(lst)
                f(buf, s, chrs, lst, k)

if __name__ == '__main__':
    s = input()
    k = int(input())

    chrs = sorted(list(set(s)))
    lst = f('', s, chrs, list(), k)

Buggy submission (verdict: Runtime Error):
s = input()
k = int(input())

sln = len(s)
subs = set()

for ln in range(1, k + 1):
    for i in range(sln):
        subs += s[i:i+ln]
print(sorted(list(subs))[k-1])

Buggy submission (verdict: Runtime Error):
def f(myC, chrs, s, lst):
    for c in chrs:
        if(myC + c) in s:
            lst += [myC + c]
            f(myC + c, chrs, s, lst)
            
if __name__ == '__main__':
    s = input()
    k = int(input())

    chrs = sorted(list(set(s)))
    lst = []
    f('', chrs, s, lst)
    ##print(lst)
    print(lst[k - 1])
Problem p03394 (python)

Fixed submission:
from random import sample
def gcd(x, y):
    if x < y:# x >= y とする
        x, y = y, x
    r = x % y
    res = y if r == 0 else gcd(y, r)
    return res

n = int(input())

nl = []
for j in range(1, 30000 + 1):
    if (j % 2 == 0 or j % 3 == 0 or j % 5 == 0):
        nl.append(j)
len_nl = len(nl)

while True:
    tl = sample(nl, len_nl)
    g = tl[0]
    total = 0
    for j in range(n):
        g = gcd(g, tl[j])
        total += tl[j]
    if total % 30 != 0:
        continue
    if g != 1:
        continue
    break
print(*tl[:n])

Buggy submission (verdict: Runtime Error):
from random import sample
from math import gcd

n = int(input())

nl = []
for j in range(1, 30000 + 1):
    if (j % 2 == 0 or j % 3 == 0 or j % 5 == 0):
        nl.append(j)
len_nl = len(nl)

while True:
    tl = sample(nl, len_nl)
    g = 0
    total = 0
    for j in range(n):
        g = gcd(g, tl[j])
        total += tl[j]
    if total % 30 == 0:
        continue
    if g != 1:
        continue
    break
print(*tl[:n])
Problem p03404 (python)

Fixed submission:
def main():
    BK = '#'
    WH = '.'

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

    g = []
    for _ in range(50):
        g.append([BK] * 100)  # 100にし忘れていた
    for _ in range(50):
        g.append([WH] * 100)

    r, c = 1, 1
    for _ in range(A - 1):
        g[r][c] = WH
        c += 2
        if c > 99:
            c = 1
            r += 2

    r, c = 51, 1
    for _ in range(B - 1):
        g[r][c] = BK
        c += 2
        if c > 99:
            c = 1
            r += 2

    print(100, 100)
    for row in g:
        print(*row, sep='')


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    BK = '#'
    WH = '.'

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

    g = []
    for _ in range(50):
        g.append([BK] * 50)
    for _ in range(50):
        g.append([WH] * 50)

    r, c = 1, 1
    for w_cnt in range(A - 1):
        g[r][c] = WH
        c += 2
        if c > 99:
            c = 1
            r += 2

    r, c = 51, 1
    for b_cnt in range(B - 1):
        g[r][c] = BK
        c += 2
        if c > 99:
            c = 1
            r += 2

    print(100, 100)
    for row in g:
        print(*row, sep='')


if __name__ == '__main__':
    main()
Problem p03427 (python)

Fixed submission:
n = input()
n_length = len(n)

ans = -1
if int(n) < 10:
    ans = int(n)
else:
    flg = True
    for i in range(1, n_length):
        if n[i] != '9':
            flg = False
            break
    if flg:
        ans = sum(map(int, list(n)))
    else:
        ans = 9 * (n_length - 1) + int(n[0]) - 1
print(ans)

Buggy submission (verdict: Runtime Error):
N = list(input())
if len(N) == 1:
    print(int(N))
else:
    print((len(N) - 1) * 9 + (int(N[0]) - 1))
Problem p03448 (python)

Fixed submission:
a= int(input())
b= int(input())
c= int(input())
x= int(input())

ret = 0
for ia in range(0, a+1):
    for ib in range(0, b+1):
        for ic in range(0, c+1):
            if 500*ia + 100*ib + 50*ic == x:
                ret += 1
print(ret)

Buggy submission (verdict: Runtime Error):
a= int(input())
b= int(input())
c= int(input())
x= int(input())

ret = 0
for ia in range(0, a+1):
    for ib in range(0, b+1):
        for ic in range(0, c+1):
            if 500*ia + 100*ib + 50*ic == x:
                ret += 1
return ret
Problem p03457 (python)

Fixed submission:
def BlCannotGo(dt, dx, dy): ## 行けないならTrue
    if (dt % 2) != ((dx + dy) % 2) or (dx + dy) > dt:
        return True
    else:
        return False

if __name__ == '__main__':
    n = int(input())
    l = list(list(map(int, input().split())) for _ in range(n))

    dt = l[0][0]
    dx = l[0][1]
    dy = l[0][2]
    if BlCannotGo(dt, dx, dy):
        print('No')    
        exit()
        
    for i in range(1,n):
        dt = l[i][0] -  l[i-1][0] 
        dx = l[i][1] -  l[i-1][1]
        dy = l[i][2] -  l[i-1][2]
        if BlCannotGo(dt, dx, dy):
            print('No')    
            exit()

    print('Yes')

Buggy submission (verdict: Runtime Error):
def BlCannotGo(dt, dx, dy): ## 行けないならTrue
    dist = dx + dy
    if (dt % 2) != (dist % 2) or dist > dt:
        return True
    else:
        return False

def abs(x,y):
    return max(x,y) - min(x,y)

if __name__ == '__main__':
    n = int(input())
    t, x, y = list(), list(), list()
    t[0], x[0], y[0] = 0, 0, 0
    for i in range(n):
        t[i+1], x[i+1], y[i+1] = map(int, input().split())

    for i in range(1,n+1):
        dt = t[i] -  t[i-1]
        dx = abs(x[i] -  x[i-1])
        dy = abs(y[i] -  y[i-1])
        if BlCannotGo(dt, dx, dy):
            print('NO')    
            exit()

    print('YES')

Buggy submission (verdict: Runtime Error):
def BlCannotGo(dt, dx, dy): ## 行けないならTrue
    dist = dx + dy
    if (dt % 2) != (dist % 2) or dist > dt:
        return True
    else:
        return False

if __name__ == '__main__':
    n = int(input())
    t, x, y = list(), list(), list()
    t[0], x[0], y[0] = 0, 0, 0
    for i in range(n):
        t[i+1], x[i+1], y[i+1] = map(int, input().split())

    for i in range(1,n+1):
        dt = t[i] -  t[i-1]
        dx = abs(x[i] -  x[i-1])
        dy = abs(y[i] -  y[i-1])
        if BlCannotGo(dt, dx, dy):
            print('NO')    
            exit()

    print('YES')
Problem p03488 (python)

Fixed submission:
# https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2017/1216_arc087
# https://pitsbuffersolution.com/compro/atcoder/arc087d.php

# 最初の移動以外は、どんな操作手順後であっても、正負いずれの方向にも動けるのがミソ

def solve(s, x, y):
    X = 0
    Y = 1

    def update(move):
        st = set()
        for p in reachable[st_ind]:
            st.add(p + move)
            st.add(abs(p - move))
        reachable[st_ind] = st
        # 絶対値の等しい正負の値を取りうるので、正だけ扱う

    n = len(s)
    spl = map(len, s.split('T'))
    x -= next(spl)
    # ここでxを減らすと、
    # 個々のmove後のx,yは、原点対象になるので、正の座標の到達点だけ扱えばよくなる

    reachable = [{0}, {0}]
    st_ind = 1
    for move in spl:
        update(move)
        st_ind ^= 1

    return (abs(x) in reachable[X]) and (abs(y) in reachable[Y])
    # x,yが負であっても、それに対応した正の値が集合に含まれていれば、到達可能


if __name__ == '__main__':
    s = input()
    x, y = map(int, input().split())
    print('Yes' if solve(s, x, y) else 'No')

Buggy submission (verdict: Runtime Error):
def main():
    *CMDs, = map(len, input().split('T'))
    CMDs += [0, 0, 0]  # 番兵,sliceでREを出さないため
    X, Y = map(int, input().split())
    X -= CMDs[0]  # この操作だけは対称性がない

    def is_reachable(cmds, goal):
        SFT = 8000
        # [-SFT,SFT] -> [0,SFT*2]
        dp = 1 << SFT
        for d in cmds:
            dp = (dp >> d) | (dp << d)
        return (dp >> (SFT + goal)) & 1

    cond = is_reachable(CMDs[2::2], X) and is_reachable(CMDs[1::2], Y)
    print('Yes' if cond else 'No')


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    *CMDs, = map(len, input().split('T'))
    CMDs += [0, 0]  # 番兵,sliceでREを出さないため
    X, Y = map(int, input().split())
    X -= CMDs[0]  # この操作だけは対称性がない

    def is_reachable(cmds, goal):
        SFT = 8000
        # [-SFT,SFT] -> [0,SFT*2]
        dp = 1 << SFT
        for d in cmds:
            dp = (dp >> d) | (dp << d)
        return (dp >> (SFT + goal)) & 1

    cond = is_reachable(CMDs[2::2], X) and is_reachable(CMDs[1::2], Y)
    print('Yes' if cond else 'No')


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    *CMDs, = map(len, input().split('T'))
    X, Y = map(int, input().split())
    X -= CMDs[0]  # この操作だけは対称性がない

    def is_reachable(cmds, goal):
        SFT = 8000
        # [-SFT,SFT] -> [0,SFT*2]
        dp = 1 << SFT
        for d in cmds:
            dp = (dp >> d) | (dp << d)
        return (dp >> (SFT + goal)) & 1

    cond = is_reachable(CMDs[2::2], X) and is_reachable(CMDs[1::2], Y)
    print('Yes' if cond else 'No')


if __name__ == '__main__':
    main()
Problem p03589 (python)

Fixed submission:
N = int(input())

w = -1
flg = False
for h in range(1, 3500 + 1):
    for n in range(h, 3500 + 1):
        q = 4 * n * h - N * (n + h)
        #print(h, n, p, q)
        if q > 0:
            #q == 0: 1/wなしで4/Nに等しくなり不適（w無限大）
            #q < 0: p > 0より、w < 0となり不適
            p = N * n * h
            if p % q == 0:
                w = p // q
                flg = True
                break
    if flg:
        break
print(h, n, w)

Buggy submission (verdict: Runtime Error):
n = int(input())

for x in range(1, 3500 + 1):
    for y in range(1, 3500 + 1):
        p = n * x * y
        q = 4 * x * y - n * (x + y)
        if p % q == 0:
            print(x, y, p // q)
            exit()

Buggy submission (verdict: Runtime Error):
n = int(input())

for x in range(1, 3500 + 1):
    for y in range(1, 3500 + 1):
        p = n * x * y
        q = 4 * x * y - n * (x + y)
        if p % q == 0:
            print(p, q, p // q)
            break
Problem p03638 (python)

Fixed submission:
h, w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
a = [None] + a

ans = [[None] * w for _ in range(h)]

cur = 1
way = 1
r, c = 0, 0
flg = True
while cur <= n:
    ans[r][c] = cur
    a[cur] -= 1
    if a[cur] == 0:
        cur += 1

    if (w == 1) or ((c == 0 or c == w - 1) and (not flg)):
        r += 1
        way *= -1
        flg = True
    else:
        c += way
        flg = False
    # print(r, c)

for aa in ans:
    print(*aa)

Buggy submission (verdict: Runtime Error):
h, w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
a = [None] + a

ans = [[None] * w for _ in range(h)]

cur = 1
way = 1
r, c = 0, 0
flg = True
while cur <= n:
    ans[r][c] = cur
    a[cur] -= 1
    if a[cur] == 0:
        cur += 1
    if (c == 0 or c == w - 1) and (not flg):
        r += 1
        way *= -1
        flg = True
    else:
        c += way
        flg = False
    # print(r, c)

for aa in ans:
    print(' '.join(map(str, aa)))

Buggy submission (verdict: Runtime Error):
h, w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
a = [None] + a

ans = [[None] * w for _ in range(h)]

cur = 1
way = 1
r, c = 0, 0
flg = True
while cur <= n:
    ans[r][c] = cur
    a[cur] -= 1
    if a[cur] == 0:
        cur += 1
    if (c == 0 or c == w - 1) and (not flg):
        r += 1
        way *= -1
        flg = True
    else:
        c += way
        flg = False
    # print(r, c)

for aa in ans:
    print(*aa)
Problem p03837 (python)

Fixed submission:
inf = 1000 * 1000 + 10

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

g = tuple([inf] * n for _ in range(n))
e = set()
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
    e.add((a, b, c))

for i in range(n):
    g[i][i] = 0

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])

# print(g)

need = set()
for a, b, c in e:
    for s in range(n):
        for t in range(n):
            if g[s][t] == g[s][a] + c + g[b][t]:
                need.add((a, b))
                break
        else:
            continue
        break
# print(need)
print(m - len(need))

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush
from math import inf


def dijkstra_need_edge(s):
    used = [False] * n
    used[s] = True

    dist = [inf] * n
    dist[s] = 0

    hq = []
    for e in g[s]:
        heappush(hq, e)

    need_edge = set()
    while hq:
        w, t, ind = heappop(hq)
        if used[t]: continue
        need_edge.add(ind)
        used[t] = True
        dist[t] = w
        add_es = map(lambda x: (dist[t] + x[0], x[1], x[2]), g[t])
        for e in add_es:
            heappush(hq, e)
    return need_edge


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

g = tuple(set() for _ in range(n))
for ind in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a].add((c, b, ind))
    g[b].add((c, a, ind))

st = set()
for v in range(n):
    st |= dijkstra_need_edge(v)
print(m - len(st))
Problem p04013 (python)

Fixed submission:
def na(): return map(int, input().split())
n, a = na()
x = list(na())
xa = list(map(lambda f: f-a, x))
'''
dp[i][点数] = パターン数
i番目まで使用したときの点数になるパターン数
'''
dp = [dict() for _ in range(n)]
if xa[0] == 0:
    dp[0][0] = 2
else:
    dp[0][0] = 1
    dp[0][xa[0]] = 1
for i in range(1, n):
    #xa[i]を採用する / 採用しないで2つに分岐
    #すべて採用しないと点数0になるので、最後に点数0になったパターン数から1引く
    for k, v in dp[i-1].items():#k:得点, v:パターン数
        score = xa[i] + k
        dp[i][score] = dp[i].get(score, 0) + v#xa[i]を採用
        dp[i][k] = dp[i].get(k, 0) + v#xa[i]を不採用
print(dp[n-1][0] - 1)

Buggy submission (verdict: Runtime Error):
def ary3(x, y, z, v): return [[[v for _  in range(z)] for _ in range(y)] for _ in range(x)]

n, a = map(int, input().split())
x = list(map(int, input().split()))
m = max(x)
dp = ary3(n + 1, n + 1, m * n + 1, 0)#(選べる枚数（範囲）0 ~ n, 選んだ枚数0 ~ n, 合計0 ~ n * max(x)) = パターン数

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

for i in range(1, n + 1):
    for j in range(1, i + 1):
        for s in range(m * n + 1):
            if s + x[i - 1] < m * n + 1:
                dp[i][j][s + x[i-1]] += dp[i - 1][j - 1][s]
            dp[i][j][s] += dp[i - 1][j][s]

ans = 0
for j in range(1, n + 1):
    ans += dp[n][j][j * a]

print(ans)
Problem p02585 (python)

Fixed submission:
n, k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = -10**18
for now in range(n):
	ruisekiwa = []
	tansaku = set()
	for i in range(n+1):
		targ = p[now]-1
		if len(ruisekiwa) >= 1:
			ruisekiwa.append(c[targ]+ruisekiwa[-1])
		else:
			ruisekiwa.append(c[targ])
		if targ in tansaku:
			break
		now = targ
		tansaku.add(targ)
	#print(ruisekiwa)
	if len(ruisekiwa) >= k:
		tr = max(ruisekiwa[:k])
		#print(tr)
		ans = max(ans, tr)
	else:
		if ruisekiwa[0] < ruisekiwa[-1]:
			#print(ruisekiwa[-1]-ruisekiwa[0])
			ms = (k//(len(ruisekiwa)-1))*(ruisekiwa[-1]-ruisekiwa[0])
			#print(ms)
			#print(len(ruisekiwa))
			#print(ruisekiwa[:k%(len(ruisekiwa)-1)+1])
			if k%(len(ruisekiwa)-1) >= 1:
				tr = max(max(ruisekiwa[:k%(len(ruisekiwa)-1)])+ms, max(ruisekiwa)+ms-(ruisekiwa[-1]-ruisekiwa[0]))
			else:
				tr = max(ruisekiwa[:-1])+ms-(ruisekiwa[-1]-ruisekiwa[0])
			#print(tr)
			ans = max(ans, tr)
		else:
			tr = max(ruisekiwa)
			ans = max(ans, tr)
print(ans)

Buggy submission (verdict: Runtime Error):
n, k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = -10**18
for now in range(n):
	ruisekiwa = []
	tansaku = set()
	for i in range(n+1):
		targ = p[now]-1
		if len(ruisekiwa) >= 1:
			ruisekiwa.append(c[targ]+ruisekiwa[-1])
		else:
			ruisekiwa.append(c[targ])
		if targ in tansaku:
			break
		now = targ
		tansaku.add(targ)
	#print(ruisekiwa)
	if len(ruisekiwa) >= k-1:
		tr = max(ruisekiwa[:k])
		#print(tr)
		ans = max(ans, tr)
	else:
		if ruisekiwa[0] < ruisekiwa[-1]:
			#print(ruisekiwa[-1]-ruisekiwa[0])
			ms = (k//(len(ruisekiwa)-1))*(ruisekiwa[-1]-ruisekiwa[0])
			#print(ms)
			tr = max(max(ruisekiwa[:k%(len(ruisekiwa)-1)])+ms, max(ruisekiwa)+ms-(ruisekiwa[-1]-ruisekiwa[0]))
			#print(tr)
			ans = max(ans, tr)
		else:
			tr = max(ruisekiwa)
			ans = max(ans, tr)
print(ans)

Buggy submission (verdict: Runtime Error):
n, k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = -10**18
for now in range(n):
	ruisekiwa = []
	tansaku = set()
	for i in range(n+1):
		targ = p[now]-1
		if len(ruisekiwa) >= 1:
			ruisekiwa.append(c[targ]+ruisekiwa[-1])
		else:
			ruisekiwa.append(c[targ])
		if targ in tansaku:
			break
		now = targ
		tansaku.add(targ)
	#print(ruisekiwa)
	if len(ruisekiwa) >= k:
		tr = max(ruisekiwa[:k])
		#print(tr)
		ans = max(ans, tr)
	else:
		if ruisekiwa[0] < ruisekiwa[-1]:
			#print(ruisekiwa[-1]-ruisekiwa[0])
			ms = (k//(len(ruisekiwa)-1))*(ruisekiwa[-1]-ruisekiwa[0])
			#print(ms)
			tr = max(max(ruisekiwa[:k%(len(ruisekiwa)-1)])+ms, max(ruisekiwa)+ms-(ruisekiwa[-1]-ruisekiwa[0]))
			#print(tr)
			ans = max(ans, tr)
		else:
			tr = max(ruisekiwa)
			ans = max(ans, tr)
print(ans)