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

e=enumerate
n,a=open(0)
n=int(n)
d=[0]+[1e18]*n
for j,(a,i)in e(sorted((-int(a),i)for i,a in e(a.split()))):d=[min(t+a*abs(~i-j+k+n),d[k-1]+a*abs(~i+k))for k,t in e(d)]
print(-min(d))

### FIXED CODE ###

e=enumerate
n,*a=map(int,open(0).read().split())
dp=[0]
for j,(a,i)in e(sorted((a,i)for i,a in e(a))[::-1]):dp=[dp[0]+a*abs(n-j-i-1)]+[max(dp[k]+a*abs(n-j+k-i-1),dp[k-1]+a*abs(i-k+1))for k in range(1,j+1)]+[dp[j]+a*abs(i-j)]
print(max(dp))
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
maze = []
for _ in range(H):
    maze.append(list(input()))


def bfs(initial):
    # goal判定はなく、一番遠いところで返す
    frontier = deque()
    frontier.append((initial, None))
    # tuple
    explored = {initial}
    while len(frontier):
        locations = []
        current_node = frontier.popleft()
        current_state = current_node[0]
        x, y = current_state
        if (x + 1 < H) and (maze[x + 1][y] != '#'):
            locations.append((x + 1, y))
        # 上に行けるかの判定
        if (x - 1 >= 0) and (maze[x - 1][y] != '#'):
            locations.append((x - 1, y))
        # 右に行けるかの判定
        if (y + 1 < W) and (maze[x][y + 1] != '#'):
            locations.append((x, y + 1))
        # 左に行けるかの判定
        if (y - 1 >= 0) and (maze[x][y - 1] != '#'):
            locations.append((x, y - 1))
        for child in locations:
            if str(child) in [str(i) for i in explored]:
                continue
            explored.add(child)
            frontier.append((child, current_node))
    return current_node


def node_to_path_count(node):
    counter = 0
    while node[1] is not None:
        counter += 1
        node = node[1]
    return counter


ans = 0
for x in range(H):
    for y in range(W):
        if maze[x][y] == '.':
            solution = bfs((x, y))
            counter = node_to_path_count(solution)
            if ans < counter:
                ans = counter

print(ans)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
maze = []
for _ in range(H):
    maze.append(list(input()))


def bfs(initial):
    # goal判定はなく、一番遠いところで返す
    distance = [[-1] * W for _ in range(H)]
    frontier = deque()
    frontier.append(initial)
    distance[initial[0]][initial[1]] = 0
    while len(frontier):
        current_node = frontier.popleft()
        x, y = current_node
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_x, new_y = x + i, y + j
            if 0 <= new_x < H and 0 <= new_y < W:
                if maze[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    frontier.append((new_x, new_y))
    return distance[x][y]


ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            continue
        solution = bfs((i, j))
        if ans < solution:
            ans = solution

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

n=int(input())
s=input()
a=0
for i in range(1000):
    t=str(i).zfill(3)
    p=0
    for j in s:
        if j==t[p]:
            p+=1
        if p==3:
            #print(t,p)
            break
    if p==3:
        a+=1
print(a)

### FIXED CODE ###

n=int(input())
s=input()
a=0
for i in range(1000):
    t=str(i).zfill(3)
    p=0
    for j in s:
        if j==t[p]:
            p+=1
        if p==3:
            #print(t,p)
            break
    if p==3:
        a+=1
print(a)
### BUGGY CODE ###

B,W=map(int,input().split())
mod=10**9+7
kaijo=[1]
Xdiv=[1]
two=pow(2,mod-2,mod)
for i in range(1,1+B+W):
    kaijo.append((kaijo[-1])*i%mod)
    Xdiv.append((Xdiv[-1]*two)%mod)
from collections import deque
gyaku=deque()
gyaku.append(pow(kaijo[B+W],mod-2,mod))
for i in range(B+W,0,-1):
    gyaku.appendleft((gyaku[0]*i)%mod)
def conb(a,b):
    return (kaijo[a]*gyaku[a-b]*gyaku[b])%mod
Blost,Wlost=0,0
if B==W:
    for k in range(1,B):
        print(two)
    for k in range(B,B+W):
        print(((1+Wlost-Blost)%mod*two)%mod)
        Blost=(Blost+conb(k-1,B-1)*Xdiv[k])%mod
        Wlost=(Wlost+conb(k-1,W-1)*Xdiv[k])%mod
    print(((1+Wlost-Blost)%mod*two)%mod)
elif B<W:
    for k in range(1,B):
        print(two)
    for k in range(B,W):
        print(((1+Wlost-Blost)%mod*two)%mod)
        Blost=(Blost+conb(k-1,B-1)*Xdiv[k])%mod
    for k in range(W,B+W):
        print(((1+Wlost-Blost)%mod*two)%mod)
        Blost=(Blost+conb(k-1,B-1)*Xdiv[k])%mod
        Wlost=(Wlost+conb(k-1,W-1)*Xdiv[k])%mod
    print(((1+Wlost-Blost)%mod*two)%mod)
elif B>W:
    for k in range(1,W):
        print(two)
    for k in range(W,B):
        print(((1+Wlost-Blost)%mod*two)%mod)
        Wlost=(Wlost+conb(k-1,W-1)*Xdiv[k])%mod
    for k in range(B,B+W):
        print(((1+Wlost-Blost)%mod*two)%mod)
        Blost=(Blost+conb(k-1,B-1)*Xdiv[k])%mod
        Wlost=(Wlost+conb(k-1,W-1)*Xdiv[k])%mod
    print(((1+Wlost-Blost)%mod*two)%mod)

### FIXED CODE ###

B,W=map(int,input().split())
mod=10**9+7
kaijo={0:1}
Xdiv={0:1}
two=pow(2,mod-2,mod)
for i in range(1,1+B+W):
    kaijo[i]=(kaijo[i-1]*i)%mod
    Xdiv[i]=(Xdiv[i-1]*two)%mod
gyaku={B+W:pow(kaijo[B+W],mod-2,mod)}
for i in range(B+W,0,-1):
    gyaku[i-1]=(gyaku[i]*i)%mod
def conb(a,b):
    if a<b:return 0
    return (kaijo[a]*gyaku[a-b]*gyaku[b])%mod
Blost,Wlost=0,0
for k in range(1,B+W):
    print(((1+Wlost-Blost)*two)%mod)
    Blost=(Blost+conb(k-1,B-1)*Xdiv[k])%mod
    Wlost=(Wlost+conb(k-1,W-1)*Xdiv[k])%mod
print(((1+Wlost-Blost)*two)%mod)
### BUGGY CODE ###

import numpy as np

n,m = map(int,input().split())
a_list = []
c = []

for i in range(m):
    a,b = map(int,input().split())
    a_list.append(a)
    c.append(sum(1 << j-1 for j in list(map(int,input().split()))))

inf = 10**10
dp = [inf]*(1 << n)
dp[0] = 0

for i in range(1 << n):
    for j in range(m):
        dp[c[j]|i] = min(dp[c[j]|i],dp[i]+a_list[j])

if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

n,m = map(int,input().split())
a_list = []
c = []

for i in range(m):
    a,b = map(int,input().split())
    a_list.append(a)
    c.append(sum(1 << j-1 for j in list(map(int,input().split()))))

inf = 10**10
dp = [inf]*(1 << n)
dp[0] = 0

for i in range(1 << n):
    for j in range(m):
        dp[c[j]|i] = min(dp[c[j]|i],dp[i]+a_list[j])

if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

from itertools import combinations

n = int(input())
h = list(map(lambda x: int(x), input().split(' ')))

r = list(combinations(range(0, n), 2))

count = 0

for i in r:
  a, b = i
  if abs(a - b) == h[a] + h[b]:
    count += 1

print(count)


### FIXED CODE ###

n = int(input())
a = list(map(lambda x: int(x), input().split(' ')))

m = {}

count = 0

for i, v in enumerate(a):
  p = i + v

  if not p in m:
    m[p] = 1
  else:
    m[p] += 1

for i, v in enumerate(a):
  p = i - v

  if p in m:
    count += m[p]

print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
for k in range(61):
    o = 0
    for i in range(N):
        if A[i]>>k &1:o+=1
    ans+=(2**k)*o*(N-o)
print(ans%(10**9+7))

### FIXED CODE ###

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

mod = pow(10,9)+7

K = 60
P = [0]*K
Z = [0]*K
for a in A:
    n = a
    for i in range(K):
        b = n%2
        if b:P[i]+=1
        else:Z[i]+=1
        n//=2
ans = 0
for k in range(K):
    ans+=(pow(2,k,mod)*(P[k]*Z[k]))%mod
print(ans%mod)
### BUGGY CODE ###

n, k = map(int, input().split())
r, s, p = map(int, input().split())
T = str(input())
score = 0
lose = []
def janken(hand):
    if hand == 'r':
        return(p)
    if hand == 's':
        return(r)
    if hand == 'p':
        return(s)

for i in range(n):
    if i <= k - 1:
        score += janken(T[i])
    else:
        if T[i] == T[i - k]:
            if i - k not in lose:
                lose.append(i)
            else:
                score += janken(T[i])
        else:
            score += janken(T[i])
print(score)

### FIXED CODE ###

n, k = map(int, input().split())
r, s, p = map(int, input().split())
T = str(input())
score = 0
lose = []
def janken(hand):
    if hand == 'r':
        return(p)
    if hand == 's':
        return(r)
    if hand == 'p':
        return(s)

for i in range(n):
    if i <= k - 1:
        score += janken(T[i])
    else:
        if T[i] == T[i - k]:
            if i - k not in lose:
                lose.append(i)
            else:
                score += janken(T[i])
        else:
            score += janken(T[i])
print(score)
### BUGGY CODE ###

S = input()
N = len(S)
t = [1 for i in range(N)]
for p in range(2 * 10 ** 5):
  t = [t[1] * (S[1] == "L")] + [t[i-1] * (S[i-1] == "R") + t[i+1] * (S[i+1] == "L") for i in range(1, N-1)] + [t[N-2] * (S[N-2] == "R")] 
print(*t)

### FIXED CODE ###

S = input()
N = len(S)
k = [0]
result = [0] * N

for i in range(N-1):
  if S[i] != S[i+1]:
    k.append(i+1)
l = [k[i+1] - k[i] for i in range(len(k) - 1)] + [N - k[-1]]

for i in range(1, len(k), 2):
  result[k[i]] += (l[i] + 1) // 2 + l[i-1] // 2
  result[k[i]-1] += l[i] // 2 + (l[i-1] + 1) // 2
print(*result)
### BUGGY CODE ###

import  itertools
n,m,q=map(int,input().split())

t=[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    a-=1
    b-=1
    t.append([a,b,c,d])

def judge(l):
    cv=[1 for h in range(n)]
    for i in range(q):
        if l[i]==1:
            cv[t[i][1]]=cv[t[i][0]]+t[i][2]
    for i in range(n):
        if cv[i]>m:
            return False
    for i in range(q):
        if l[i]==1:
            if cv[t[i][1]]-cv[t[i][0]]!=t[i][2]:
                return False
    return True

num=[0,1]
ans=0

for df in itertools.product(num,repeat=q):
    ty=list(df)
    if judge(ty):
        to=0

        for i in range(q):
            if ty[i]==1:
                to+=t[i][3]
        ans=max(ans,to)

print(ans)




### FIXED CODE ###

import  itertools
n,m,q=map(int,input().split())

t=[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    a-=1
    b-=1
    t.append([a,b,c,d])

def judge(l):
    ans=0
    for i in range(q):
        a,b,c,d=t[i]
        if l[b]-l[a]==c:
            ans+=d
    return ans

num=[]
ans=0
for i in range(1,m+1):
    num.append(i)

for df in itertools.combinations_with_replacement(num,n):

    ty=list(df)
    f=judge(ty)
    ans=max(ans,f)

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

while True:
    try:
        N = int(input())
        if N>0 or N<=100:
            A = []
            for i in range(0,N):
              B = int(input())
              if B>0 or B<=100:
                  A.append(B)

            sum1 = 1/A[0]

            for i in range(0,N-1):
              sum1 = sum1 + 1/A[i+1]

            result = 1/sum1
            print(result)

            break

    except:
            print("Error")

### FIXED CODE ###

try:
    N = int(input())
    if N>0 or N<=100:
        S = input()
        A = S.split()
        A = list(map(int, A)) 
 
        sum1 = 1/A[0]
 
        for i in range(0,N-1):
         sum1 = sum1 + 1/A[i+1]
 
        result = 1/sum1
        print(result)

except:
        print("Error")
### BUGGY CODE ###

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

inv = [i for i in range(N-1)]
visited = [1]

path = [[] for i in range(N)]

for i in range(M):
  A, B = map(int, input().split())
  path[A-1].append(B)
  path[B-1].append(A)
nows = [1]
for t in range(N):
  buf = []
  buf2 = []
  for now in nows:
    buf2 = buf2 + path[now-1]
  buf2 = set(buf2)
  buf3 = set(visited)
  buf2 = buf2 - buf3
  for p in buf2:
    buf.append(p)
    visited.append(p)
    inv[p-2]=now
  if len(buf)==0:
    break
  nows = buf
print("Yes")
for i in inv:
  print(i)


### FIXED CODE ###

import queue

q = queue.Queue()
N, M = map(int, input().split())

ans = [-1 for i in range(N+1)]
path = [[] for i in range(N+1)]

for i in range(M):
  A, B = map(int, input().split())
  path[A].append(B)
  path[B].append(A)
q.put(1)
COUNTER = 0
while not q.empty() :
  now = q.get()
  for p in path[now]:
    if ans[p]==-1:
      ans[p]=now
      q.put(p)
      #print(COUNTER, now,p)
      COUNTER+=1
      
print("Yes")
for i in ans[2:]:
  print(i)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def LCS(s, t):
	n, m = len(s), len(t)
	dp = [[0 for i in range(m+1)] for j in range(n+1)]
	for i in range(n+1):
		for j in range(m+1):
			if i == 0 or j == 0:
				dp[i][j] = 0
			elif s[i-1] == t[j-1]:
				dp[i][j] = 1 + dp[i-1][j-1]
			else:
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
	# print("    ", end="")
	# for i in t:print(i, end = " ")
	# s += " "
	# # print("\n")
	# for k in range(n+1):
	# 	print(s[k-1], *dp[k])
	index = dp[n][m]
	ans = [" "]*index
	i, j = n, m
	while index:
		if s[i-1] == t[j-1]:
			ans[index-1] =  s[i-1]
			index -= 1
			i -= 1; j -= 1
		elif dp[i-1][j] > dp[i][j-1]:
			i -= 1
		else:
			j -= 1
	return(("").join(ans))

def solve():
	s1 = input().strip(); s2 = input().strip()
	print(LCS(s1, s2))









if __name__ == "__main__":
	solve()

### FIXED CODE ###

import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

def LCS(s, t):
	n, m = len(s), len(t)
	dp = [[0 for i in range(m+1)] for j in range(n+1)]
	for i in range(n+1):
		for j in range(m+1):
			if i == 0 or j == 0:
				dp[i][j] = 0
			elif s[i-1] == t[j-1]:
				dp[i][j] = 1 + dp[i-1][j-1]
			else:
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
	index = dp[n][m]
	ans = [" "]*index
	i, j = n, m
	while index:
		if s[i-1] == t[j-1]:
			ans[index-1] =  s[i-1]
			index -= 1
			i -= 1; j -= 1
		elif dp[i-1][j] > dp[i][j-1]:
			i -= 1
		else:
			j -= 1
	return(("").join(ans))

def solve():
	s1 = inp().strip(); s2 = inp().strip()
	print(LCS(s1, s2))


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

n = int(input())

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

l.sort(reverse = True)
ans = 1
for i in range(n):
    ans *= l[i]
    if ans > 10**18:
      ans = -1
      break
    if 0 in l:
      ans = 0
      break

print(ans)

### FIXED CODE ###

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

l.sort(reverse = True)
ans = l[-1]
for i in range(n-1):
    ans *= l[i]
    if ans > 10**18:
      ans = -1
      break
    elif ans == 0:
      ans = 0
      break

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

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

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

ans = ans % 1000000007
print(ans)

### FIXED CODE ###

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

s = sum(a)
ans = 0
mod = 10 ** 9 + 7

for i in range(n-1):
    s -= a[i]
    ans += a[i] * s % mod

ans = ans % mod
print(ans)
### BUGGY CODE ###

import sys
import heapq as hq
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

base = 10 ** 10
sb = [-(b[i] * base + i) for i in range(N) if a[i] != b[i]]
hq.heapify(sb)
res = 0
while len(sb):
  v = hq.heappop(sb)
  i = -v % base
  v = -v // base
  if v < a[i]:
    print(-1)
    exit(0)
  d = v - a[i]
  x = b[i - 1] + b[(i + 1) % N]
  if d // x == 0:
    if v == a[i]: continue
    print(-1)
    exit(0)
  b[i] -= x * (d // x)
  res += d // x
  hq.heappush(sb, -(b[i] * base + i))
print(res)

### FIXED CODE ###

import sys
from heapq import heappush as hpu
from heapq import heappop as hpo
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

base = 10 ** 6
sb = [-(b[i] * base + i) for i in range(N) if a[i] != b[i]]
h = []
for t in sb: hpu(h, t)
res = 0
while len(h):
  v = hpo(h)
  i = -v % base
  v = -v // base
  if v < a[i]:
    print(-1)
    exit(0)
  d = v - a[i]
  x = b[i - 1] + b[(i + 1) % N]
  t = d // x
  if t == 0:
    if v == a[i]: continue
    print(-1)
    exit(0)
  b[i] -= x * (t)
  res += t
  hpu(h, -(b[i] * base + i))
print(res)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
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[k] >= l[j] + l[i]:
                break
            if l[j] < l[k] + l[i] and l[i] < l[k] + l[j]:
                ans += 1
print(ans)

### FIXED CODE ###

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

def prime(i):
    if i == 1:
        return False
    if (i > 2) & (i % 2 == 0):
        return False
    for j in range(3, int(i**(0.5)) + 1, 2):
        if i % j == 0:
            return False
    return True



q = int(input())
for _ in range(q):
    ans = 0
    l, r = map(int, input().split())
    for i in range(l, r+2, 2):
        if prime(i) & prime(int(i+1)//2):
            ans += 1
    print(ans)

### FIXED CODE ###

def Eratosthenes(n):
    prime_list = [True for _ in range(n + 1)]
    prime_list[0] = False
    prime_list[1] = False
    for j in range(4, n + 1, 2):
        prime_list[j] = False
    prime_list[2] = True
    for i in range(3, int(n ** 0.5) + 1, 2):
        if prime_list[i]:
            for j in range(i * 2, n + 1, i):
                prime_list[j] = False
    return prime_list


def prime_2017(prime_list):
    prime_2017_list = [True for _ in range(len(prime_list))]
    for i in range(len(prime_list)):
        if i <= 2:
            prime_2017_list[i] = False
        elif prime_list[i]:
            if not prime_list[(i + 1) // 2]:
                prime_2017_list[i] = False
        else:
            prime_2017_list[i] = False
    return prime_2017_list

q = int(input())
num_list = []
num_max = 0
for _ in range(q):
    l, r = map(int, input().split())
    num_list.append([l, r])
    num_max = max(r, num_max)
prime_list = Eratosthenes(num_max)
prime_2017_list = prime_2017(prime_list)
prime_num = [0 for _ in range(num_max + 1)]
for i in range(num_max):
    prime_num[i + 1] = prime_num[i] + prime_2017_list[i + 1]

for l, r in num_list:
    print(prime_num[r] - prime_num[l - 1])
### BUGGY CODE ###

#AIsing2020 d

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        a = X10
        if (a>>(i-1) & 1) and X10_num1 >1:
            a -= 2**(i-1)
            amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)

        elif (a>>(i-1) & 1) and X10_num1 ==1:
            print(0)
            continue
        else:
            a += 2**(i-1)
            amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)
        nc = amari 
        if a ==0:
            co = 0
        else:
            co = 1
            while nc >0:
                bin_str = bin(nc)
                cou1 = bin_str.count('1')
                nc = nc%cou1
                co +=1
        
        print(co)


main()


### FIXED CODE ###

#AIsing2020 d

def f(n):
        cnt = 0
        while n:
            cnt+= 1
            n = n%bin(n).count('1')
        return cnt

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        j = N-i
        if (X[j] == '1') and X10_num1 >1:
            mod = X10_num1-1
            amari = (X10_ninus - pow(2,i-1,mod))%(mod) 
        elif (X[j] == '1') and X10_num1 ==1:
            print(0)
            continue
        else:
            mod = X10_num1+1
            amari = (X10_pulse + pow(2,i-1,mod))%(mod)

        print(1+f(amari))


main()
### BUGGY CODE ###

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

counts = Counter(A)

for i in A:
    ans = 0
    for n, count in counts.items():
        temp = count
        if n == i:
            temp -= 1
        if temp < 2:
            continue
        ans += len(list(itertools.combinations(range(temp), 2)))
    print(ans)

### FIXED CODE ###

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

def choose2(n):
    return n * (n - 1) // 2

counts = Counter(A)
total = 0
for n, count in counts.items(): 
    #初めに、同じ数同士から2つ選んだ時の組み合わせの総和を求める
    combi = choose2(count)
    total += combi 

for i in A:
    #上で求めた組み合わせの総和から、消える数字について1つ減らしたときの組み合わせを減らす
    temp = total - choose2(counts[i])
    temp += choose2(counts[i] - 1) 
    print(temp)
### BUGGY CODE ###

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

ans=-float('inf')

def get_loop_score(start): # return loop len and its loop score
    now_p=0
    visited=set()
    nxt=p[start]-1

    while True:
        nxt=p[nxt]-1
        if nxt in visited:
            break
        visited.add(nxt)
        now_p+=c[nxt]
    return now_p

def simulate(start,nokori): # ret max possible score
    now_p=0
    nxt=p[start]-1
    cnt=0
    p_lis=[]


    while True:
        nxt=p[nxt]-1
        visited.add(nxt)
        now_p+=c[nxt]
        p_lis.append(now_p)
        cnt+=1
        if cnt==nokori:
            break

    return max(p_lis)
  
for i in range(n):
    p_lis=[]

    cnt=0
    now_p=0
    nxt=p[i]-1

    visited=set()

    while True:
        now_p+=c[nxt]
        nxt=p[nxt]-1
        p_lis.append(now_p)

        cnt+=1
        if cnt==k:
            break

        if k>10000 and nxt in visited:
#            print(visited)
            break
        visited.add(nxt)

    if cnt!=k: # loop detected
#        print(i,p_lis)
        nokori = k-cnt
        loop_score=get_loop_score(nxt)
        if loop_score <= 0: # no loop
            nokori=len(visited)
        else: # loop as much as possible
            loops = nokori//len(visited) - 1
            now_p+= loops*loop_score
            nokori = loops*len(visited)

#        print("loop score:",loop_score)
        score = simulate(nxt,nokori)
        p_lis.append(score)

#    print(i,max(p_lis))

    ans=max(ans,max(p_lis))

print(ans)

### FIXED CODE ###

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

def sim(start,mx): # simulate mx step from start, returns max_score
    if mx==0:
        return 0
    now_p=0
    nxt=p[start]-1
    cnt=0
    p_lis=[]

    while True:
        nxt=p[nxt]-1
        now_p+=c[nxt]
        p_lis.append(now_p)
        cnt+=1
        if cnt==mx:
            break

    return max(p_lis)

visited_p=set() # already checked flag
cycle_score=[] # cycle loop score
cycle_points=[]
now_cycle=0

for i in range(n):
    if i in visited_p:
        continue
    visited_p.add(i)
    now_p=0
    nxt=p[i]-1
    visited=set()
    while True:
        nxt=p[nxt]-1
        visited_p.add(nxt)
        if nxt in visited:
            break
        visited.add(nxt)
        now_p+=c[nxt]
    cycle_score.append(now_p)
    cycle_points.append(list(visited))

ans=-float('inf')

for c_num in range(len(cycle_score)):
#    print(c_num,cycle_score[c_num],cycle_points[c_num])
    cycle_len=len(cycle_points[c_num])
    for start in cycle_points[c_num]:

        if cycle_score[c_num]<0: # no loop, just check min(loop_len,k)
            score = sim(start,min(cycle_len,k))
            ans=max(ans,score)

        else: # loop as many as possible
            loop_num = max(0,(k // cycle_len) - 1)
            nokori=k-loop_num*cycle_len
            score = sim(start,nokori) + loop_num*cycle_score[c_num]
            ans=max(ans,score)

print(ans)