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

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

# AtCoder Grand Contest
# Problem A


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    count = 0

    for i in range(n):
        count += sum([1 for j in range(i, n) if sum(a[i:j + 1]) == 0])

    print(count)


### FIXED CODE ###

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

# AtCoder Grand Contest
# Problem A


if __name__ == '__main__':
    from collections import Counter

    n = int(input())
    a = [0] + list(map(int, input().split()))
    s = [0] * len(a)

    for i in range(1, n + 1):
        s[i] += s[i - 1] + a[i]

    print(sum([si * (si - 1) // 2 for si in Counter(s).values()]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    n, s = map(int, input().split())
    a = [int(i) for i in input().split()]
    MOD = 998244353

    dp = [0] * (s + 1)
    dp[0] = 1

    for i in a:
        p = [0] * (s + 1)
        dp, p = p, dp
        for j in range(s + 1):
            dp[j] += (p[j] * 2) % MOD
            dp[j] %= MOD
            if (ji := j + i) <= s:
                dp[ji] = (dp[ji] + p[j]) % MOD

    print(dp[s])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline


def main():
    n, s = map(int, input().split())
    A = [int(i) for i in input().split()]

    MOD = 998244353

    dp = np.zeros(s + 1, dtype="int32")
    dp[0] = 1

    for a in A:
        p = (dp * 2) % MOD
        p %= MOD
        p[a:] += dp[:-a]
        dp = p % MOD

    print(dp[s])


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

def warshall_floyd(d):
    #d[i][j]=i番目の頂点からj番目の頂点までの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
import copy

n,m=map(int,input().split())
way_list=[[100 for i in range(n)] for j in range(n)]
for i in range(n):
    way_list[i][i]=0
#自分から自分の値はもちろんゼロ
#way_list[i][j]頂点iからjまでの最短距離
lists=[]
for i in range(m):
    a,b=map(int,input().split())
    way_list[a-1][b-1]=1
    way_list[b-1][a-1]=1
    lists.append((a,b))
#最短距離が100以下であれば十分到達可能
#そうでないなら到達は不可能
answer=0
for i in range(m):
    sub=copy.deepcopy(way_list)
    x,y=lists[i][0],lists[i][1]
    sub[x-1][y-1]=100
    sub[y-1][x-1]=100
    #一度この頂点がないものとして計算してみる
    P=warshall_floyd(sub)
    
    flag=True
    for i in range(n):
        for j in range(n):
            if P[i][j]>=100:
                flag=False
                #到達不可能な点が出た時→絶対必要な点
    if not flag:
        answer+=1
print(answer)

### FIXED CODE ###

n,m=map(int,input().split())
lists=[]
for _ in range(m):
    a,b=map(int,input().split())
    lists.append([a,b])

answer=0

for some  in range(m):
    ans=0
    for i in range(1,n+1):
        cnt=0
        for _ in lists:
            if _[0]==i or _[1]==i:
                cnt+=1
                index=lists.index(_) 
        if cnt==1:
            ans+=1
            del lists[index]
        else:
            ans+=0
            continue
    answer+=ans
print(answer)
### BUGGY CODE ###

input()
ns = [n for n in input()]
 
answers = []
first = []
second = []
third = []
 
for i in range(len(ns) - 2):
  if i in first:
    continue
  else:
    first.append(i)
  for j in range(i+1, len(ns) - 1):
    if ''.join([ns[i], ns[j]]) in second:
      continue
    else:
      second.append(''.join([ns[i], ns[j]]))
    for k in range(j+1, len(ns)):
      answers.append(''.join([ns[i], ns[j], ns[k]]))
print(len(set(answers)))

### FIXED CODE ###

input()
ns = [n for n in input()]
 
scores = 0
first = []
second = []
third = []
third_nums = None
 
for i in range(len(ns) - 2):
  if ns[i] in first:
    continue
  else:
    first.append(ns[i])
  for j in range(i+1, len(ns) - 1):
    if ''.join([ns[i], ns[j]]) in second:
      continue
    else:
      second.append(''.join([ns[i], ns[j]]))
      third_nums = set(ns[j+1:])
      scores += len(third_nums)
      
print(scores)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if l[i]<l[j]+l[k] and l[j]<l[k]+l[i] and l[k]<l[i]+l[j]:
                ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l2=sorted(l)
box=[0] #各長さの棒が何本あるか　最初の０は数合わせ
ans=0

num=1
while num<l2[0]: #最小の棒までは０をappend
    box.append(0)
    num+=1
    
now=l2[0]
bounum=1
for i in range(1,n):
    if l2[i]!=now:
        box.append(bounum)
        next=now+1
        while next<l2[i]:
            box.append(bounum)
            next+=1 
        now=l2[i]
        bounum+=1
    else:
        bounum+=1
if len(box)!=l2[-1]+1:
    box.append(bounum) #boxの完成

for i in range(n-2):
    for j in range(i+1,n-1):
        c=l2[i]+l2[j]-1
        if c>l2[-1]:
            c=l2[-1]
        add=box[c]-(j+1)
        if add<0:
            add=0
        ans+=add

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

from collections import deque

def main():
    n, x, y = map(int, input().split())
    dist = [[None]*n for _ in range(n)]
    cnt = [0]*n
    q = deque()
    
    for i in range(n):
        q.appendleft([i, 0])
        dist[i][i] = 0
        while q:
            j, d = q.pop()
            cnt[d] += 1
            if j > 0 and dist[i][j-1] is None:
                dist[i][j-1] = d+1
                q.appendleft([j-1, d+1])
            if j < n-1 and dist[i][j+1] is None:
                dist[i][j+1] = d+1
                q.appendleft([j+1, d+1])
            if j == x-1 and dist[i][y-1] is None:
                dist[i][y-1] = d+1
                q.appendleft([y-1, d+1])
            elif j == y-1 and dist[i][x-1] is None:
                dist[i][x-1] = d+1
                q.appendleft([x-1, d+1])
    for i in range(1, n):
        print(cnt[i]//2)
                

if __name__ == "__main__":
    main()

### FIXED CODE ###

# D問題
from collections import deque
def main():
    n, x, y = map(int, input().split())
    x -= 1
    y -= 1
    inf = 10**5
    ans = [0]*n
    q = deque()
    for i in range(n):
        dist = [inf]*n
        q.appendleft(i)
        dist[i] = 0
        while q:
            v = q.pop()
            d = dist[v]
            if v-1 >= 0 and dist[v-1] == inf:
                q.appendleft(v-1)
                dist[v-1] = d+1
            if v+1 <= n-1 and dist[v+1] == inf:
                q.appendleft(v+1)
                dist[v+1] = d+1
            if v == x and dist[y] == inf:
                q.appendleft(y)
                dist[y] = d + 1
            if v == y and  dist[x] == inf:
                q.appendleft(x)
                dist[x] = d + 1
        for di in dist:
            ans[di] += 1
    for a in ans[1:]:
        print(a//2)

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

def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=[[-inf for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0

  #DP
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
      else: #入る可能性はない
        dp[i+1][w]=dp[i][w]
  return dp[N][W]

N,W = map(int,input().split(' '))
WEIGHT = []
VALUE = []
for i in range(N):
  w,v = map(int,input().split(' '))
  WEIGHT.append(w)
  VALUE.append(v)
print(knapsack(N,W,WEIGHT,VALUE))
              

### FIXED CODE ###

def DP():
    n,W = map(int, input().split(' '))
    WV = (map(int, input().split(' ')) for _ in range(n))
    dp = [0] * (W+1)

    for w, v in WV:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(DP())
### BUGGY CODE ###

import numpy as np
import bisect as bs
import sys
input = sys.stdin.readline

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

A.sort()
B.sort()
C.sort()

second = [N - bs.bisect_right(C,B[i]) for i in range(N)]

ans = 0
for i in range(N):
    ans += np.sum(second[bs.bisect_right(B,A[i]):])

print(int(ans))

### FIXED CODE ###

import numpy as np
import bisect
import sys
input = sys.stdin.readline

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

A.sort()
B.sort()
C.sort()

ans=0
len_C = len(C)
for b in B:
    a = bisect.bisect_left(A,b)
    c = len_C - bisect.bisect_right(C,b)
    ans += a*c

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

def solve(i,m):
	if m == 0:
		return True
	if i >= n:
		return False
	res = solve(i+1,m) or solve(i+1,m-A[i])
	return res

n = int(input())
A = input()
A = [int(s) for s in A.split()]
q = int(input())
m = input()
m = [int(s) for s in m.split()]

ans = [{True:'yes',False:'no'}[solve(0,mm)] for mm in m]
print('\n'.join(ans))

### FIXED CODE ###

def solve(i,m):
	if m == 0:
		return True
	if i >= n:
		return False
	res = solve(i+1,m) or solve(i+1,m-A[i])
	return res

n = int(input())
A = input()
A = [int(s) for s in A.split()]
q = int(input())
m = input()
m = [int(s) for s in m.split()]

ans = []
s = sum(A)
for mm in m:
	if s < mm:
		ans.append('no')
	else:
		ans.append({True:'yes',False:'no'}[solve(0,mm)])
#ans = [{True:'yes',False:'no'}[solve(0,mm)] for mm in m]
print('\n'.join(ans))
### BUGGY CODE ###

import sys
# sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    s = input()
    q = input_int()
    for _ in range(q):
        data = input().split()
        if len(data) == 1:
            s = s[::-1]
        else:
            if data[1] == "1":
                s = data[2] + s
            else:
                s = s + data[2]
    print(s)
    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
# sys.setrecursionlimit(100000)
from collections import deque


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    s = deque(list(input()))
    q = input_int()
    inverse = False
    for _ in range(q):
        data = input().split()
        if len(data) == 1:
            inverse = not inverse
        else:
            if (data[1] == "1" and not inverse) or (data[1] == "2" and inverse):
                s.appendleft(data[2])
            else:
                s.append(data[2])
    if inverse:
        print("".join(reversed(s)))
    else:
        print("".join(s))
    return


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

n, t = map(int, input().split())
dishes = []

for _ in range(n):
    time, point = map(int, input().split())
    dishes.append([time, point])

dishes.sort()

DP = [0] * t

candidates = []
for time, point in dishes:
    candidates.append(max(DP) + point)

    for i in range(t-1, time-1, -1):
        DP[i] = max(DP[i], DP[i-time]+point)

print(max(candidates))

### FIXED CODE ###

from collections import defaultdict


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

dish = []

for _ in range(n):
    time, point = map(int, input().split())
    dish.append([time, point])

dish.sort()
DP = [[0]*t for i in range(n+1)]
ans = defaultdict(int)

for i in range(1, n+1):
    time, point = dish[i-1]

    for j in range(t):
        DP[i][j] = max(DP[i-1][j], DP[i][j])
        if j + time >= t:
            ans[i] = max(DP[i-1][j]+point, ans[i])
            continue
        DP[i][j+time] = max((DP[i-1][j] + point), DP[i-1][j+time])

res = max(ans.values())
print(res)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
B_C = [list(map(int, input().split())) for j in range(M)]

B = [B_C[j][0] for j in range(M)]
C = [B_C[j][1] for j in range(M)]

A.sort()
for j in range(M):
    for i in range(B[j]):
        if A[i] < C[j]:
            A[i] = C[j]
    A.sort()
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
B_C = [list(map(int, input().split())) for j in range(M)]

B_C = sorted(B_C, key=lambda x:x[1], reverse=True)

B = [B_C[j][0] for j in range(M)]
C = [B_C[j][1] for j in range(M)]

D = []
for j in range(M):
    D += [C[j]] * B[j]
    if len(D) >= N:
        break

A.sort()

for i in range(N):
    if A[i] < D[i]:
        A[i] = D[i]
    else:
        break
    if i == len(D) - 1:
        break

print(sum(A))
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
r=[0]*(n-1)
t=[0]*(n)
dr={}
dt={l[0]:[0]}
for i in range(1,n):
  x=i-l[i]
  y=i+l[i]
  if x in dr:
    dr[x].append(i)
  else:
    dr[x]=[i]
  if y in dt:
    dt[y].append(i)
  else:
    dt[y]=[i]
ans=0
for x in dr.keys():
  if x>0 and x in dt:
    y=dr[x]
    z=dt[x]
    for w in y:
      for ww in z:
        if w>ww:
          ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
r=[0]*(n-1)
t=[0]*(n)
dr={}
dt={l[0]:[0]}
for i in range(1,n):
  x=i-l[i]
  y=i+l[i]
  if x in dr:
    dr[x].append(i)
  else:
    dr[x]=[i]
  if y in dt:
    dt[y].append(i)
  else:
    dt[y]=[i]
ans=0
for x in dr.keys():
  if x>0 and x in dt:
    y=dr[x]
    z=dt[x]
    ans+=len(z)*len(y)
print(ans)
### BUGGY CODE ###

import sys
INF=100000000
def frog(i,K,h,dp):
    global INF
    if dp[i]!=INF:
        return dp[i]
    else:
        if i==1:
            dp[i]=0
            return dp[i]
        elif i==2:
            dp[i]=abs(h[1]-h[0])
            return dp[i]
        else:
            cost=[]
            for k in range(1,K+1):
                if i-k-1>=0:
                    cost.append(frog(i-k,K,h,dp)+abs(h[i-1]-h[i-k-1]))
                else:
                    break
            dp[i]=min(cost)
            return dp[i]
sys.setrecursionlimit(INF)
N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[INF for i in range(N+1)]
print(frog(N,K,h,dp))


### FIXED CODE ###

import numpy as np
N,K=map(int,input().split())
h=list(map(int,input().split()))
h=np.array(h)
cost=np.zeros(N+1)
cost[1]=0
cost[2]=abs(h[1]-h[0])
for i in range(3,N+1):
    x=1 if i-K<=1 else i-K
    cost[i]=(cost[x:i]+abs(h[i-1]-h[x-1:i-1])).min()
print(int(cost[N]))
### BUGGY CODE ###

import math
K = int(input())
t = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for l in range(1,K+1):
            t += math.gcd(math.gcd(i,j),l)
print(t)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
K = int(input())
t = 0
t1 = 0
t2 = 0
for i in range(1,K+1):
    for j in range(i,K+1):
        for l in range(j,K+1):
            if i == j == l:
                t = t + i
            elif i == j or j ==l or l ==i:
                t = t + 3 * gcd(i, j,l)
            else:
                t = t + 6 * gcd(i,j,l)
             
           
           
print(t)
### BUGGY CODE ###

import math
from fractions import gcd

def is_prime(n):
  if n == 1: 
    return 1

  for k in range(2, int(math.sqrt(n)) + 1):
    if n % k == 0:
      return 0

  return 1
  
a, b = map(int, input().split())
ans = 0
for i in range(1, min(a, b) + 1):
  if i > 7 and (i % 2 == 0 or i % 3 == 0 or i % 5 == 0 or i % 7 == 0):
    pass
  else:
    if a % i == 0 and b % i == 0:
      ans += is_prime(i)
    
print(ans)
    


### FIXED CODE ###

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table
  
a, b = map(int, input().split())
la = prime_decomposition(a)
lb = prime_decomposition(b)
la_lb_and = list(set(la) & set(lb))
    
print(len(la_lb_and) + 1)
### BUGGY CODE ###

count = 0
scounts = []
N = int(input())
for n in range(N):
    s = sorted(input())
    found = False
    index = -1
    for i in range(len(scounts)):
        # print("s="+str(s))
        if scounts[i][0] == s:
            # print("EQUALS : "+str(scounts[i][0])+" == "+str(s))
            found = True
            count += scounts[i][1]
            scounts[i][1] += 1
            break
        elif scounts[i][0] > s:
            # print("MORE THAN : "+str(scounts[i][0])+" > "+str(s))
            index = i
            break
        else: # scounts[i][0] > s:
            pass
            # print("LESS THAN : "+str(scounts[i][0])+" < "+str(s))

    # print("index="+str(index))
    if not found:
        if index<0:
            # print("append(["+str(s)+",1]")
            scounts.append([s,1])
        else:
            # print("insert("+str(index)+",["+str(s)+",1]")
            scounts.insert(index, [s, 1])

        # print(str(s))
        # print("DONE: "+str(scounts))
    # print("===")
print(count)


### FIXED CODE ###

ss = []
N = int(input())
for n in range(N):
    s = sorted(input())
    ss.append(s)

ss = sorted(ss)

total = 0
count = 0
for n in range(N):
    if n==0:
        continue
    # print("ss["+str(n-1)+"]="+str(ss[n-1]))
    # print("ss["+str(n)+"]="+str(ss[n]))
    if ss[n-1]==ss[n]:
        count += 1
    else:
        total += int(count*(count+1)/2)
        count = 0
    # print("===")
total += int(count*(count+1)/2)
count = 0

print(int(total))
### BUGGY CODE ###

count = int(input())
su_list = list(map(int, input().split()))
ans_list = []
for i in range(1, count + 1):
    ans_list.append(su_list.count(i))
for j in ans_list:
    print(j)

### FIXED CODE ###

import collections
count = int(input())
su_list = list(map(int, input().split()))
c = collections.Counter(su_list)
for i in range(1, count + 1):
    print(c[i])
### BUGGY CODE ###


import fractions
from functools import reduce


k = int(input())

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

k += 1
ans = 0

for i in range(1,k):
    for j in range(i,k):
        #print(i,j)
        if i == j:
            ans += gcd(i,j)
        else:
            ans += gcd(i,j)*6

for i in range(1,k):
    for j in range((i+1),k):
        for h in range((j+1),k):
            #print(i,j,h)
            ans += gcd(i,j,h)*6


print(ans)


### FIXED CODE ###

import math
from functools import reduce


k = int(input())

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k += 1
ans = 0

for i in range(1,k):
    for j in range(i,k):
        #print(i,j)
        if i == j:
            ans += gcd(i,j)
        else:
            ans += gcd(i,j)*6

for i in range(1,k):
    for j in range((i+1),k):
        for h in range((j+1),k):
            #print(i,j,h)
            ans += gcd(i,j,h)*6


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

"""
A = 3, B = 4
[青青青][赤赤赤赤][青青青][赤赤赤]...

N = 8
[青青青赤赤赤赤青]

return 青 = 4
"""

def count_balls():
    # 入力
    N, A, B = map(int, input().split())
    # N以下の[青*A][赤*B]の組み合わせの個数
    i = 1
    while True:
        if N >= (A+B) * i:
            i += 1
        else:
            break
    # N - ([青*A]+[赤*B])*i
    remainder = N - (A+B) * (i-1)
    if remainder <= A:
        return A * (i-1) + remainder
    else:
        return A * (i-1) + A

result = count_balls()
print(result)

### FIXED CODE ###

"""
A = 3, B = 4
[青青青][赤赤赤赤][青青青][赤赤赤]...

N = 8
[青青青赤赤赤赤青]

return 青 = 4
"""

def count_balls():
    # 入力
    N, A, B = map(int, input().split())
    # [青青青赤赤赤赤]の個数と余り
    comb_count = N // (A + B)
    remainder = N % (A + B)
    # 集計
    if remainder <= A:
        return A * comb_count + remainder
    else:
        return A * comb_count + A

result = count_balls()
print(result)
### BUGGY CODE ###

N = int(input())

height = input()
height = height.split()
height = [int(s) for s in height]

count = 0

for i in range(N):
  for j in range(i+1, N):
    if j-i == height[i] + height[j]:
      count += 1

print(count)

### FIXED CODE ###

import collections

N = int(input())

height = input()
height = height.split()
height = [int(s) for s in height]

count = 0


d = dict(collections.Counter([i + height[i] for i in range(N)]))
ans = sum([d.get(i - height[i], 0) for i in range(N)])
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    p_lst = list(map(int, input().split()))

    ans = 0

    for i in range(n):
        if min(p_lst[:i + 1]) >= p_lst[i]:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    p_lst = list(map(int, input().split()))

    min_val = n + 1
    ans = 0

    for i in range(n):
        if min_val > p_lst[i]:
            min_val = p_lst[i]
            ans += 1

    print(ans)


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

n, k = map(int, input().split())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

ans = - 10 ** 18
for i in range(1, n+1):
    base = i
    nxt = p[i]
    cnt = 0
    score = 0
    while True:
        cnt += 1
        if cnt > k:
            break
        score += c[nxt]
        ans = max(ans, score)
        #print("i = ", i, "ans = ", ans, "score = ", score)
        if nxt == base:
            break
        nxt = p[nxt]
    if cnt >= k:
        continue
    extra = k - cnt
    score_tmp = score
    nxt = p[nxt]
    nxt_tmp = nxt
    for j in range(min(extra, cnt)):
        score += c[nxt]
        ans = max(ans, score)
        #print("ans = ", ans, "score = ", score, "nxt = ", nxt, "c[nxt] = ", c[nxt])
        nxt = p[nxt]
    #print("score = ", score, "ans = ", ans)
    score = score_tmp
    nxt = nxt_tmp
    a = extra // cnt
    if extra % cnt == 0:
        a -= 1
    score += score * max(a, 0)
    ans = max(ans, score)
    for j in range(extra - a * cnt):
        score += c[nxt]
        ans = max(ans, score)
        #print("ans = ", ans, "score = ", score, "nxt = ", nxt, "c[nxt] = ", c[nxt])
        nxt = p[nxt]

print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

ans = - 10 ** 18
for i in range(1, n+1):
    base = i
    nxt = p[i]
    cnt = 0
    score = 0
    while True:
        cnt += 1
        if cnt > k:
            break
        score += c[nxt]
        ans = max(ans, score)
        #print("i = ", i, "ans = ", ans, "score = ", score)
        if nxt == base:
            break
        nxt = p[nxt]
    if cnt >= k:
        continue
    extra = k - cnt
    score_tmp = score
    nxt = p[nxt]
    nxt_tmp = nxt
    for j in range(min(extra, cnt)):
        score += c[nxt]
        ans = max(ans, score)
        #print("ans = ", ans, "score = ", score, "nxt = ", nxt, "c[nxt] = ", c[nxt])
        nxt = p[nxt]
    #print("score = ", score, "ans = ", ans)
    score = score_tmp
    nxt = nxt_tmp
    a = extra // cnt
    if extra % cnt == 0:
        a -= 1
    score += score * max(a, 0)
    ans = max(ans, score)
    for j in range(extra - a * cnt):
        score += c[nxt]
        ans = max(ans, score)
        #print("ans = ", ans, "score = ", score, "nxt = ", nxt, "c[nxt] = ", c[nxt])
        nxt = p[nxt]

print(ans)