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

N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)

ans = 0
for i in range(N):
  j = N-2
  while j > i:
    k = N - 1
    while k > j:
      if L[i]-L[j]-L[k] < 0:
        ans += 1
      k -=1
    j -= 1
  
print(ans)

       

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)

ck = [0]*(N-2)
ans = 0
for i in range(N-2):
  j = i + 1
  k = N - 1
  while j < k:
    if L[i]-L[j]-L[k] < 0:
      ans += k-j
      j += 1 
    else:
      k -=1
  
print(ans)
### BUGGY CODE ###

N, K = (int(nk) for nk in input().split())
P = [(int(p)+1)/2 for p in input().split()]

max_ev = 0
for i in range(N-K+1):
    max_ev = max(max_ev, sum(P[i:i+K]))

print(max_ev)


### FIXED CODE ###

N, K = (int(nk) for nk in input().split())

curr_S = 0
count = 1
max_ev = 0
index = 0
has_eval_sk = False
zero_e = []
for p_str in input().split():
    e = (int(p_str)+1) / 2
    zero_e.append(e)
    if has_eval_sk:
        curr_S += e - zero_e[index]
        max_ev = max(max_ev, curr_S)
        index += 1
    else:
        curr_S += e
        if count == K:
            max_ev = curr_S
            has_eval_sk = True
        count += 1

print(max_ev)
### BUGGY CODE ###

from operator import mul
from functools import reduce

n=int(input())
a=list(map(int,input().split()))
limit=10**18

ans = 1
ans = reduce(mul, a) #=> 1320

# for i in range(n):
#   ans *= a[i]
#   if a[i] == 0:
#     break

if ans > limit:
  print(-1)
else:
  print(ans)


### FIXED CODE ###

# from operator import mul
# from functools import reduce

n=int(input())
a=list(map(int, input().split()))
# limit=10**18

# if 0 in a:
#     print(0)
#     exit()

ans = 1
# ans = reduce(mul, a) #=> 1320

for i in range(n):
  ans *= a[i]
  if ans > 10 ** 18:
  # if a[i] == 0:
  #   break
  # elif (ans*a[i]) > limit:
    ans = -1
    break

for i in range(n):
  if a[i] == 0:
      ans = 0

# if ans > limit:
#   print(-1)
# else:
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit((10 ** 6))
input = sys.stdin.readline
N, M, P = map(int, input().split())
INF = float('inf')
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b, c = a - 1, b - 1, c - P
    G[a].append((b, -c))

check = [False] * N


def dfs(u, used):
    if used[u]:
        return
    used[u] = True
    for w, c in G[u]:
        dfs(w, used)


def dfs2(u, dest):
    used = [False] * N
    dfs(u, used)
    check[u] = used[dest]


dist = [INF] * N
for i in range(N):
    dfs2(i, N - 1)

dist[0] = 0
for i in range(N):
    update = False
    for e in range(N):
        for w, c in G[e]:
            if not check[e] or not check[w] or dist[e] == INF:
                continue
            if dist[w] > dist[e] + c:
                dist[w] = dist[e] + c
                update = True

    if not update:
        break
    if i == N - 1:
        print(-1)
        exit()

print(max(0, -dist[N - 1]))

### FIXED CODE ###

import sys
sys.setrecursionlimit((10 ** 6))
input = sys.stdin.readline
N, M, P = map(int, input().split())
INF = float('inf')
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b, c = a - 1, b - 1, c - P
    G[a].append((b, -c))
dist = [INF] * N
dist[0] = 0
for i in range(N):
    for e in range(N):
        for w, c in G[e]:
            if dist[e] != INF and dist[w] > dist[e] + c:
                dist[w] = dist[e] + c

ans = -dist[N - 1]
is_negative = [False] * N
for i in range(N):
    for e in range(N):
        for w, c in G[e]:
            if dist[e] != INF and dist[w] > dist[e] + c:
                dist[w] = dist[e] + c
                is_negative[w] = True

            if is_negative[e]:
                is_negative[w] = True

if is_negative[N - 1]:
    print(-1)
else:
    print(max(ans, 0))
### BUGGY CODE ###

N = int(input())
for h in range(1, 3500):
  for n in range(1, 3500):
    a = N*h*n
    b = 4*h*n - n*N - N*h
    if b > 0 and a%b == 0:
      print(h, n, a//b)
      exit()

### FIXED CODE ###

N = int(input())
for h in range(1, 3500):
  for n in range(1, 3500):
    a = N*h*n
    b = 4*h*n - n*N - N*h
    if b > 0 and a%b == 0:
      print(h, n, a//b)
      exit()
### BUGGY CODE ###

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

M = 10**6

import math

setwise = A[0]
for i in range(1,N):
    setwise = math.gcd(setwise,A[i])
    
PrimeFactorss = [[] for _ in range(M+1)]
for i in range(2, M+1):
    if len(PrimeFactorss[i]) == 0:
        for x in range(i, M+1, i):
            PrimeFactorss[x].append(i)
num_list = [0]*(M+1)

for i in range(N):
    num_list[A[i]] += 1

pairwise = [0]*N

for i in range(N):
    num_list[A[i]] -= 1
    for j in PrimeFactorss[A[i]]:
        for k in range(j,M+1,j):

            if num_list[k]==1:
                pairwise[i] += 1
                
    num_list[A[i]] += 1
    
if sum(pairwise) == 0:
    print("pairwise coprime")
elif setwise == 1:
    print("setwise coprime")
else:
    print("not coprime")


### FIXED CODE ###

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

M = 10**6

import math

setwise = A[0]
for i in range(1,N):
    setwise = math.gcd(setwise,A[i])
    
PrimeFactorss = [[] for _ in range(M+1)]
for i in range(2, M+1):
    if len(PrimeFactorss[i]) == 0:
        for x in range(i, M+1, i):
            PrimeFactorss[x].append(i)
num_list = [0]*(M+1)

for i in range(N):
    num_list[A[i]] += 1

pairwise = [0]*(M+1)

n=M
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)

for i in primes:
    for j in range(i,M+1,i):
        if num_list[j]==1:
            pairwise[i] += 1
        
ans = 0    
for i in pairwise:
    if i>1:
        ans += 1
        break
    
if setwise == 1 and ans == 0:
    print("pairwise coprime")
elif setwise == 1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
Q=int(input())
l=[0]*Q
for i in range(Q):
    l[i]=list(map(int,input().split()))
    
for i in range(Q):    
    a = [(l[i][1] if s == l[i][0] else s) for s in a]
    print(sum(a))


### FIXED CODE ###

import collections

N=int(input())
a=list(map(int,input().split()))
Q=int(input())
l=[0]*Q
for i in range(Q):
    l[i]=list(map(int,input().split()))

answer=sum(a)

b=collections.Counter(a)
    
for i in range(Q):    
    num=b[l[i][0]]
    variance=l[i][1]-l[i][0]
    answer+=variance*num
    print(answer)
    b[l[i][0]]=0
    b[l[i][1]]+=num
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().split())
a = list( map(int, input().split()))
handshakelist = np.array([0])

a = np.array(a)

for i in range(n):
    a_i = a[:(i+1)] + a[i]
    handshakelist = np.hstack((handshakelist, a_i))
    a_i[-1] = 0
    handshakelist = np.hstack((handshakelist, a_i))
handshakelist = np.sort(handshakelist)[::-1]

ans = np.sum(handshakelist[:m])

print(ans)

### FIXED CODE ###

from bisect import bisect_left
from itertools import accumulate


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

b = [0] + a
b.sort(reverse=True)
b = [0] +b
b = list(accumulate(b))

def isok(sum_):
    n_pattern = 0
    for i in range(n):
        n_pattern += n - bisect_left(a, sum_ - a[i])
        if n_pattern >= m:
            return True

    return False

ok = min(a)*2
ng = max(a)*2 +1

while ng - ok > 1:
    mid = (ok+ng)//2
    if isok(mid):
        ok = mid
    else:
        ng = mid

sum_ng = ng
sum_ok = ok

m_counter_ng = 0

ans = 0
for i in range(n):
    id_ng = bisect_left(a, sum_ng - a[i])
    ans += b[n-id_ng]
    ans += a[i]*(n - id_ng)
    m_counter_ng += n - id_ng

ans += sum_ok * (m - m_counter_ng)

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

import sys
 
input = sys.stdin.readline
 
ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

import sys
import numpy as np
import fractions
 
from functools import reduce
 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
 
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
 
def lcm_list(numbers):
    ans = 1
    for num in numbers:
        ans = ans * num // fractions.gcd(ans,num)
    return ans
 
def LI():
  return [int(s) for s in input().split()]
 
 
input = sys.stdin.readline
ri = lambda: int(input())
ril = lambda: list(map(int, input().split()))
 
N = ri()
A_s = ril()
mod = 10**9 + 7
 
l = lcm_list(A_s)
 
print(sum(map(lambda x : l//x, A_s)) % mod)

### FIXED CODE ###

import fractions
 
N = int(input())

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

A_s = LI()
mod = 10**9 + 7

#l = lcm_list(A_s)
l = 1
for num in A_s:
    l = l * num // fractions.gcd(l,num)

count = 0
for a in A_s:
  count+=l//a
  
print(count % mod)
### BUGGY CODE ###

import numpy as np
N = int(input())
A=np.array([])
for i in range(N):
    A=np.append(A, int(input()) )
max_index=np.argmax(A)
a_max=int(A[max_index])
a_second=int(np.amax(np.delete(A,max_index)))
for i in range(N):
    if i==max_index:
        print(a_second)
    else:
        print(a_max)

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array([int(input()) for i in range(N)])

max_index=np.argmax(A)
a_max=int(A[max_index])
a_second=int(np.amax(np.delete(A,max_index)))
A[:]=a_max
A[max_index]=a_second
for a in A:
    print(int(a))
### BUGGY CODE ###

h, w = map(int, input().split())
 
m = list()
mv = list()
mh = list()
 
for i in range(h):
    mh.append([0] * w)
for i in range(h):
    mv.append([0] * w)
 
for i in range(h):
    m.append(input())
 
for i in range(h):
    c = 0
    for j in range(w):
        if m[i][j] == "#":
            mh[i][j] = 0
            for k in range(c):
                mh[i][j - k - 1] = c
            c = 0
        else:
            c += 1
    for k in range(c):
        mh[i][w - 1 - k] = c
 
for i in range(w):
    c = 0
    for j in range(h):
        if m[j][i] == "#":
            mv[j][i] = 0
            for k in range(c):
                mv[j - k - 1][i] = c
            c = 0
        else:
            c += 1
    for k in range(c):
        mv[h - 1 - k][i] = c
 
res = 0
for i in range (h):
    for j in range(w):
        res = max(res, mv[i][j] + mh[i][j])
print(res - 1)

### FIXED CODE ###

h, w = map(int, input().split())

m = list()
mv = list()
mh = list()

for i in range(h):
    mh.append([0] * w)
for i in range(h):
    mv.append([0] * w)

for i in range(h):
    m.append(input())

for i in range(h):
    c = 0
    for j in range(w):
        if m[i][j] == "#":
            mh[i][j] = 0
            for k in range(c):
                mh[i][j - k - 1] = c
            c = 0
        else:
            c += 1
    for k in range(c):
        mh[i][w - 1 - k] = c

for i in range(w):
    c = 0
    for j in range(h):
        if m[j][i] == "#":
            mv[j][i] = 0
            for k in range(c):
                mv[j - k - 1][i] = c
            c = 0
        else:
            c += 1
    for k in range(c):
        mv[h - 1 - k][i] = c

res = 0
for i in range (h):
    for j in range(w):
        res = max(res, mv[i][j] + mh[i][j])
print(res - 1)
### BUGGY CODE ###

import itertools as itr

N, M = map(int, input().split())
A = [0] * M
B = [0] * M
C = []
for m in range(M):
    A[m], B[m] = map(int, input().split())
    C.append(set([int(cm) for cm in input().split()]))

INF = (10**5) * (10**3)
dp = [[INF] * 2**N for _ in range(M + 1)]
for m in range(M + 1):
    dp[m][0] = 0


def Set2Bit(st):
    bt = ["0" for _ in range(N)]
    for i in st:
        bt[i-1] = "1"
    return bt


for m in range(0, M):
    for bit in itr.product("01", repeat=N):
        pre_bit = next_bit = int("".join(bit), 2)
        dp[m+1][next_bit] = dp[m][pre_bit]
    for bit in itr.product("01", repeat=N):
        pre_bit = int("".join(bit), 2)
        key_bit = int("".join(Set2Bit(C[m])), 2)
        next_bit = pre_bit | key_bit
        dp[m+1][next_bit] = min(dp[m+1][next_bit], dp[m][next_bit], dp[m][pre_bit] + A[m])

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


### FIXED CODE ###

N, M = map(int, input().split())
A = [0] * M
B = [0] * M
C = [0]*M
for m in range(M):
    A[m], B[m] = map(int, input().split())
    C[m] = [int(cm) for cm in input().split()]

INF = 100000000
dp = [[INF] * 2**N for _ in range(M + 1)]
dp[0][0] = 0


def Set2Bit(st):
    bt = ["0"]*N
    for i in st:
        bt[i-1] = "1"
    return bt


for m in range(0, M):
    key = Set2Bit(C[m])
    key_bit = int("".join(key), 2)
    for bit in range(2**N):
        pre_bit = next_bit = bit
        dp[m+1][next_bit] = dp[m][pre_bit]
    for bit in range(2**N):
        pre_bit = bit
        next_bit = pre_bit | key_bit
        dp[m+1][next_bit] = min(dp[m+1][next_bit], dp[m][next_bit], dp[m][pre_bit] + A[m])

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

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

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

    cnt = [0] * 3
    for a in A:
        cnt[a-1] += 1

    dp = [[[0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]
    for k in range(N+1):
        for j in range(N+1):
            for i in range(N+1):
                if i+j+k > N:
                    continue
                if i > 0:
                    dp[i][j][k] += (dp[i-1][j][k] + (N / (i+j+k))) * (i / (i+j+k))
                if j > 0 and i < N:
                    dp[i][j][k] += (dp[i+1][j-1][k] + (N / (i+j+k))) * (j / (i+j+k))
                if k > 0 and j < N:
                    dp[i][j][k] += (dp[i][j+1][k-1] + (N / (i+j+k))) * (k / (i+j+k))
    print(dp[cnt[0]][cnt[1]][cnt[2]])


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

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

    cnt = [0] * 3
    for a in A:
        cnt[a-1] += 1

    dp = [[[0.] * (N+1) for _ in range(N+1)] for _ in range(N+1)]
    for k in range(N+1):
        for j in range(N+1-k):
            for i in range(N+1-j-k):
                ijk = float(i + j + k)
                if ijk == 0:
                    continue
                x = N / ijk
                tmp = 0
                if i > 0:
                    tmp += (dp[i-1][j][k] + x) * (i / ijk)
                if j > 0 and i < N:
                    tmp += (dp[i+1][j-1][k] + x) * (j / ijk)
                if k > 0 and j < N:
                    tmp += (dp[i][j+1][k-1] + x) * (k / ijk)
                dp[i][j][k] = tmp
    print(dp[cnt[0]][cnt[1]][cnt[2]])


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

import sys
input = sys.stdin.readline

mod = 998244353

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

dp = [[[0]*3 for i in range(S+1)] for j in range(N+1)]
###index


dp[0][0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp[i+1][j][0] += dp[i][j][0]
        dp[i+1][j][0] %= mod

        dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][1] %= mod

        dp[i+1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2]
        dp[i+1][j][2] %= mod

        if j+A[i] <= S:
            dp[i+1][j+A[i]][1] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+A[i]][1] %= mod
        
            dp[i+1][j+A[i]][2] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+A[i]][2] %= mod

print(dp[N][S][2])

### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 998244353

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

dp0 = [[0]*(S+1) for _ in range(N+1)]
dp1 = [[0]*(S+1) for _ in range(N+1)]
dp2 = [[0]*(S+1) for _ in range(N+1)]
###dp[i][j][k]:Aのindex[i-1]まで見て和がjになっているもの
###kの意味は解説の通り


dp0[0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp0[i+1][j] += dp0[i][j]
        dp0[i+1][j] %= mod

        dp1[i+1][j] += dp0[i][j] + dp1[i][j]
        dp1[i+1][j] %= mod

        dp2[i+1][j] += dp0[i][j] + dp1[i][j] + dp2[i][j]
        dp2[i+1][j] %= mod

        if j+A[i] <= S:
            dp1[i+1][j+A[i]] += dp0[i][j] + dp1[i][j]
            dp1[i+1][j+A[i]] %= mod
        
            dp2[i+1][j+A[i]] += dp0[i][j] + dp1[i][j]
            dp2[i+1][j+A[i]] %= mod

print(dp2[N][S])
### BUGGY CODE ###

n = int(input())
A = [i for i in input().split(' ')] 

fl = "YES"
for i, a in enumerate(A):
  if a in A[i+1:]:
    fl = "NO"
    break

print(fl)


### FIXED CODE ###

n = int(input())
A = input().split(' ')

if len(A) == len(set(A)):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
P = list(map(float, input().split()))

dp = defaultdict(float)
dp[(0, 0)] = 1.0

for p in P:
    newDP = defaultdict(float)
    for (X, Y), val in dp.items():
        # 表が出る
        newDP[(X + 1, Y)] += val * p
        # 裏が出る
        newDP[(X, Y + 1)] += val * (1 - p)
    dp = newDP

ans = 0.0
for x in range(N + 1):
    y = N - x
    if x > y:
        ans += dp[(x, y)]

print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
P = np.array(input().split(), dtype=float)

dp = np.zeros(N + 1, dtype=float)
dp[0] = 1 - P[0]
dp[1] = P[0]

for i in range(N - 1):
    newDP = dp * (1 - P[i + 1])
    newDP[1:] += dp[:-1] * P[i + 1]
    dp = newDP.copy()

n = (N + 1) // 2
ans = dp[n:].sum()
print(ans)
### BUGGY CODE ###

import math
from collections import deque
n,m=[int(_) for _ in input().split()]
A=[[int(_) for _ in input().split()] for l in range(m)]
R=deque([] for _ in range(n))
for a in A:
    R[a[0]-1].append(a[1]-1)
    R[a[1]-1].append(a[0]-1)
print("Yes")
Dis=[100000000]*n
Dis[0]=0
PP=[0]*n
l=deque()
l.append(0)
while l:
    x=l.pop()
    for a in R[x]:
        if Dis[a]>Dis[x]+1:
            Dis[a]=Dis[x]+1
            l.append(a)
            PP[a]=x
for t in range(1,n):
    print(PP[t]+1)


### FIXED CODE ###

import math
from collections import deque
n,m=[int(_) for _ in input().split()]
A=[[int(_) for _ in input().split()] for l in range(m)]
R=deque([] for _ in range(n))
for a in A:
    R[a[0]-1].append(a[1]-1)
    R[a[1]-1].append(a[0]-1)
print("Yes")
Dis=deque([100000000]*n)
Dis[0]=0
PP=deque([0]*n)
l=deque()
l.append(0)
while l:
    x=l.popleft()
    for a in R[x]:
        if Dis[a]>Dis[x]+1:
            Dis[a]=Dis[x]+1
            l.append(a)
            PP[a]=x
for t in range(1,n):
    print(PP[t]+1)
### BUGGY CODE ###

x,size=map(int,input().split())
weight=[]
value=[]
for i in range(x):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[0 for i in range(size+1)] for j in range(len(weight))]
for i in range(len(weight)):
    dp[i][0]=0
for i in range(len(weight)):
    for j in range(1,size+1):
        if weight[i]>j:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
print(dp[len(value)-1][size])
        
    

### FIXED CODE ###

x,size=map(int,input().split())
weight=[]
value=[]
weight.append(0)
value.append(0)
for i in range(x):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
max_value=sum(value)
dp=[[float('inf') for i in range(max_value+1)] for j in range(x+1)]
for i in range(x+1):
    dp[i][0]=0
for i in range(1,x+1):
    w=weight[i]
    v=value[i]
    for knap_v in range(1,max_value+1):
        if v<=knap_v:
            dp[i][knap_v]=min(dp[i-1][knap_v],w+dp[i-1][knap_v-v])
        else:
            dp[i][knap_v]=dp[i-1][knap_v]
ans=0
# print(dp)
for i in range(max_value+1):
    if dp[x][i]<=size:
        ans=i
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

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

while(1):
    if m % n == 0:
        print(m//n)
        exit()
    n += 1


### FIXED CODE ###

#!/usr/bin/env python3

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

ans = 1
num = int(m**0.5)+1

for i in range(1, num):
    if m % i != 0:
        continue
    j = m//i
    if i >= n:
        ans = max(ans, j)
    if j >= n:
        ans = max(ans, i)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = -float('inf')

for i in range(n):
    start, count = i, 1
    val = c[start]
    while p[start]-1 != i:
        start = p[start]-1
        count += 1
        val += c[start]

    start = i
    if val > 0:
        a = (k//count-1)*val
        ans = max(a, ans)
        num = k%count+count
    else:
        a = 0
        num = min(k, count)

    for j in range(num):
        start = p[start]-1
        a += c[start]
        ans = max(ans, a)
print(ans)



### FIXED CODE ###

from numba import jit
@jit
def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    ans = -10**10
    
    for i in range(n):
        start, count = i, 1
        val = c[start]
        while p[start]-1 != i:
            start = p[start]-1
            count += 1
            val += c[start]

        start = i
        if val > 0:
            a = (k//count-1)*val
            ans = max(a, ans)
            num = k%count+count
        else:
            a = 0
            num = min(k, count)

        for _ in range(num):
            start = p[start]-1
            a += c[start]
            ans = max(a, ans)
    print(int(ans))

main()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from pprint import pprint

def solve(H: int, W: int, A: "List[str]"):
    count = [[H + W] * (W + 2) for _ in range(H + 2)]
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                count[i + 1][j + 1] = 0
            else:
                count[i + 1][j + 1] = min(count[i][j + 1], count[i + 1][j]) + 1

    #pprint(count)
    ret = 0
    for i in range(H, 0, -1):
        for j in range(W, 0, -1):
            count[i][j] = min(count[i][j], min(count[i][j + 1], count[i + 1][j]) + 1)
            ret = max(ret, count[i][j])
    #pprint(count)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from pprint import pprint

def solve(H: int, W: int, A: "List[str]"):
    used = [[False] * W for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, -1, 0, 1]
    s = set()
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                s.add((i, j))
                used[i][j] = True

    ret = 0
    while True:
        nex = set()
        for x, y in s:
            for j in range(4):
                tx = x + dx[j]
                ty = y + dy[j]
                if 0 <= tx < H and 0 <= ty < W and not used[tx][ty]:
                    nex.add((tx, ty))
                    used[tx][ty] = True
        if len(nex) < 1:
            break
        s = nex
        ret += 1

    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()