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

N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [0 for _ in range(N)]
for i in range(1, N):
    r = max(0, i - K)
    dp[i] = min(d + abs(H[i] - h) for d, h in zip(dp[r:i], H[r:i]))
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [0 for _ in range(N)]
for i, hi in enumerate(H):
    if i == 0:
        continue
    r = max(0, i - K)
    dp[i] = min(d + abs(hi - h) for d, h in zip(dp[r:i], H[r:i]))
print(dp[N-1])
### BUGGY CODE ###

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

def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)

def lcm(x, y):
    return x * y // gcd(x, y)

law = 10 ** 9 + 7
ans = 0
l = a[0]
for x in a:
    r = lcm(l, x)
    ans *= r // l
    ans += r // x
    ans %= law
    l = r
print(ans)

### FIXED CODE ###

MAX_PRIME = 10**3
is_prime = [1] * MAX_PRIME
primes = []
is_prime[0] = 0
is_prime[1] = 0
for i in range(MAX_PRIME):
    if is_prime[i]:
        primes.append(i)
        for j in range(2, ((MAX_PRIME-1)//i) + 1):
            is_prime[i*j] = 0

def factorization(n):
    factor = {}
    for p in primes:
        if p ** 2 > n:
            break
        while n % p == 0:
            n //= p
            if p not in factor:
                factor[p] = 1
            else:
                factor[p] += 1
    if n > 1:
        factor[n] = 1
    return factor
def extGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, y, x = extGCD(b, a%b)
    y -= a//b * x
    return g, x, y
def moddiv(a, b):
    _, inv, _ = extGCD(b, law)
    return a * inv % law

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

ans = 0
l = {}
lmod = 1
law = 10 ** 9 + 7
for x in a:
    fx = factorization(x)
    for p, c in fx.items():
        if p not in l:
            ans *= p ** c
            lmod *= p ** c
            ans %= law
            lmod %= law
            l[p] = c
        elif c > l[p]:
            ans *= p ** (c - l[p])
            lmod *= p ** (c - l[p])
            ans %= law
            lmod %= law
            l[p] = c
    b = moddiv(lmod, x)
    ans += b
    ans %= law
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
import math  # gcdもあるよ
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化
INF = 10**9 + 7

def main():
    n = int(input())
    N = list(map(int,input().split()))
    ans = 0
    for i in range(n - 1):
        #print(N[i] , sum(N[i + 1:]))
        ans += (N[i] * sum(N[i + 1:])) % INF
        ans %= INF
    print(ans)
    return 0

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import numpy as np
import math  # gcdもあるよ
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化
INF = 10**9 + 7

def main():
    n = int(input())
    N = list(map(int,input().split()))
    ans = 0
    """
    for i in range(n - 1):
        #print(N[i] , sum(N[i + 1:]))
        ans += (N[i] * sum(N[i + 1:])) % INF
        ans %= INF
    """
    # ans = sum(N)  /2
    N2 = [pow(i, 2, INF) for i in N]
    N3 = pow(sum(N), 2, INF)
    #print(N2, N3)
    N4 = (N3 - sum(N2))
    if N4 % 2 == 1:
        N4 += INF
    ans = (N4 / 2) % INF
    print(int(ans))
    return 0

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

import numpy as np

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

for i in range(n):
    x2 = x.copy()
    x2.pop(i)
    print(int(np.median(x2)))

### FIXED CODE ###

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

if n == 2:
    print(x[1])
    print(x[0])
else:
    y = sorted(x)
    m1 = y[int(n/2)-1]
    m2 = y[int(n/2)]
    if m1 == m2:
        for _ in range(n):
            print(m1)
    else:
        for i in range(n):
            if x[i] <= m1:
                print(m2)
            elif x[i] >= m2:
                print(m1)
### BUGGY CODE ###

from collections import defaultdict
 
N,W = map(int, input().split())
WV = []
for i in range(N):
    WV.append(list(map(int, input().split())))
 
dp = defaultdict(int)
 
dp[0] = 0
 
for w,v in WV:
    for nw, nv in list(dp.items()):
        if nw+w <= W:
            dp[nw+w] = max(dp[nw+w], nv+v)
            
print(max(dp.values()))

### FIXED CODE ###

from collections import defaultdict
 
N,W = map(int, input().split())
WV = []
for i in range(N):
    WV.append(list(map(int, input().split())))
 
dp = defaultdict(int)
 
dp[0] = 0
 
for w,v in WV:
    for nw, nv in list(dp.items()):
        if nw+w <= W:
            dp[nw+w] = max(dp[nw+w], nv+v)
            
print(max(dp.values()))
### BUGGY CODE ###

def main():
    N, M = map(int, input().split(" "))
    A = list(map(int, input().split(" ")))
    while M > 0:
        A.sort()
        if A[-1] == 0:
            break
        A[-1] //= 2
        M -= 1
    print(sum(A))


if __name__ == '__main__':
    main()

### FIXED CODE ###

from heapq import heapify, heappop, heappush


def negative(str):
    return -1 * int(str)


def main():
    N, M = map(int, input().split(" "))
    A = list(map(negative, input().split(" ")))
    heapify(A)
    while M > 0:
        x = heappop(A)
        heappush(A, -1 * (-1 * x // 2))
        M -= 1
    print(sum(A) * -1)


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

import itertools
mod = 10 ** 9 + 7
n=int(input())
a=list(map(int, input().split(" ")))
temp = 0
for (i, j) in itertools.combinations(a, 2):
  temp += (i * j) % mod
print(temp % mod)

### FIXED CODE ###

import itertools
mod = 10 ** 9 + 7
n=int(input())
a=list(map(int, input().split(" ")))
temp = 0
total = sum(a)
for i in a:
  temp += i * (total - i)
temp //= 2
print(temp % mod)
### BUGGY CODE ###

a, b, k = map(int, input().split())
for i in range(a, b+1):
  if i < a + k or i > b - k:
    print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
n = b - a + 1

if n > k * 2:
  for i in range(k):
    print(a+i)
  for i in range(k):
    print(b-(k-i-1))
else:
  for i in range(a, b+1):
    print(i)
### BUGGY CODE ###

N,K = map(int,input().split())
if K!=1:
    while True:
        N=abs(N-K)
        tmp=N
        if abs(N-K)>tmp:
            print(tmp)
            exit(0)
else:
    print(0)

### FIXED CODE ###

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

div =N//K
N=N-div*K

if K!=1:
    while True:
        N=abs(N-K)
        tmp=N
        if abs(N-K)>tmp:
            print(tmp)
            exit(0)
else:
    print(0)
### BUGGY CODE ###

ans = []
N, Q = map(int, input().split())
s = input()
for i in range(Q):
    l, r = map(int, input().split())
    s_q = s[l-1:r]
    ans.append( \
        (len(s_q) - len(s_q.replace('AC', '')) ) \
            // 2)

print('\n'.join(map(str, ans)))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
memo = [0]*(N+1)
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        memo[i+1] = memo[i]+1
    else:
        memo[i+1] = memo[i]
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(memo[r-1]-memo[l-1])

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

import copy
n,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n-1)]
l2=[list(map(int,input().split())) for i in range(q)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)

L4=[0 for i in range(n)]
for i in range(q):
  L4[l2[i][0]-1]+=l2[i][1]
distance=[0 for i in range(n)]
distance[0]=L4[0]
ans=[0 for i in range(n)]
ans[0]=L4[0]
L=[0]
L2=[]
L3=[]
ct=1
while len(L2)!=n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      distance[connection[L[j]][k]]=distance[L[j]]+L4[connection[L[j]][k]]
      L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=copy.copy(L3)
  L3=[]
  ct+=1
for i in range(len(distance)):
  distance[i]=str(distance[i])
print(' '.join(distance))

### FIXED CODE ###

import copy
n,q=map(int,input().split())
l=[]
for i in range(n-1):
  l.append(list(map(int,input().split())))
l2=[]
for i in range(q):
  l2.append(list(map(int,input().split())))
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)

L4=[]
for i in range(n):
  L4.append(0)
for i in range(q):
  L4[l2[i][0]-1]+=l2[i][1]
distance=[0 for i in range(n)]
distance[0]=L4[0]
ans=[0 for i in range(n)]
ans[0]=L4[0]
L=[0]
L2=[]
L3=[]
while len(L2)!=n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      distance[connection[L[j]][k]]=distance[L[j]]+L4[connection[L[j]][k]]
      L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=copy.copy(L3)
  L3=[]
for i in range(len(distance)):
  distance[i]=str(distance[i])
print(' '.join(distance))
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	s = input()
	K = INT()

	strings = set()
	for i in range(1, len(s)+1):
		for j in range(len(s)-i+1):
			strings.add(s[j:j+i])
	print(sorted(strings)[K-1])


if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	s = input()
	K = INT()

	strings = set()
	for i in range(1, K+1):
		for j in range(len(s)-i+1):
			strings.add(s[j:j+i])
	print(sorted(strings)[K-1])


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

def f(t,T):
    if t in T:
        return T[t]
    else:
        return 0

from copy import copy

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

T={}
for a in A[1:]:
    if a in T:
        T[a]+=1
    else:
        T[a]=1

F=True
for i in range(1,N):
    a,b=A[0],A[i]
    X=[a,b]+[0]*(N-2)

    U=copy(T)
    U[b]-=1

    G=True
    for k in range(N-2):
        c=a^b
        if f(c,U)>0:
            U[c]-=1
            X[k+2]=c
            a,b=b,c
        else:
            G=False
            break

    if G and X[-2]^X[-1]==X[0] and X[-1]^X[0]==X[1]:
        print("Yes")
        exit()

print("No")

### FIXED CODE ###

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

T={}
for a in A:
    if a in T:
        T[a]+=1
    else:
        T[a]=1

F=True
for x in T:
    F&=(3*T[x]%N==0)

if not F:
    print("No")
    exit()

M=max(T,key=lambda x:T[x])
if 3*T[M]==N:
    x,y,z=list(T.keys())
elif 3*T[M]==2*N:
    x=y=M
    del T[M]
    z=tuple(T.keys())[0]
else:
    x=y=z=M

if x^y==z:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import sys
from collections import defaultdict

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

def recordnum(a,b):
    if not (0 < a < H-1 and 0 < b < W-1):
        return 
    else:
        res = M[(a,b)]
        for i,j in vector:
            res += M[(a+i,b+j)]
        num[res] += 1
        return


def dfs(a,b,color):

    if visited[(a,b)]:
        return
    
    recordnum(a,b)
    visited[(a,b)] = True

    if color == "b":
        for i,j in vector:
            x = a+i
            y = b+j
            if 0 < x < H-1 and 0 < y < W-1 and not M[(x,y)]:
                dfs(x,y,"w")
    return

    

H,W,N = map(int,input().split())

M = defaultdict(int)
visited = defaultdict(int)
ab = []

for _ in range(N):
    a,b = map(int,input().split())
    ab.append([a-1,b-1])
    M[(a-1,b-1)] = 1


vector = [[0,1],[0,-1],[1,0],[-1,0],[1,1],[-1,-1],[1,-1],[-1,1]]
num = [0]*10

for a,b in ab:
    dfs(a,b,"b")

num[0] = (H-2)*(W-2) - sum(num)

for i in num:
    print(i)

### FIXED CODE ###

"""
参考(神様)
https://atcoder.jp/contests/abc045/submissions/6046010
"""

###かぶるやつを考える.例えばあるマスのかぶり値が9だとしたら,
###周囲はすべて黒->j=9のが1つとカウントしてよい,他の値についても同様.

import sys
from collections import defaultdict,Counter

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

H,W,N = map(int,input().split())

covered = defaultdict(int)
vector = [(0,0),(0,1),(0,-1),(1,0),(-1,0),(1,1),(-1,-1),(1,-1),(-1,1)]

for _ in range(N):
    a,b = map(int,input().split())

    for i,j in vector:
        x = a+i-1
        y = b+j-1

        if 0 < x < H-1 and 0 < y < W-1:
            covered[(x,y)] += 1

num = Counter(covered.values())
##print(num)
num[0] = (H-2)*(W-2)-sum(num.values())

for i in range(10):
    print(num[i])
### BUGGY CODE ###

n = int(input())
a = map(int, input().split())
ans = 1
for i in a:
    ans *= i
if 1000000000000000000 < ans:
    ans = -1
print (ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
if 0 in a:
    print (0)
else:
    for i in a:
        ans *= i
        if 1000000000000000000 < ans:
            ans = -1
            break
    print (ans)
### BUGGY CODE ###

n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353

dp=[[0]*s for _ in range(n)]    

for i in range(n):
    if a[i]<=s:
        dp[i][a[i]-1]=2**i%mod
    for j in range(s):
        if i>0:
            dp[i][j]+=dp[i-1][j]*2
            dp[i][j]%=mod
            if j+a[i]<s:
                dp[i][j+a[i]]+=dp[i-1][j]
                dp[i][j+a[i]]%=mod
            
print(dp[n-1][s-1])

### FIXED CODE ###

n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353

dp=[[0]*s for _ in range(n)]    
tmp=1
for i in range(n):
    if a[i]<=s:
        dp[i][a[i]-1]=tmp
    for j in range(s):
        if i>0:
            dp[i][j]+=dp[i-1][j]*2
            dp[i][j]%=mod
            if j+a[i]<s:
                dp[i][j+a[i]]+=dp[i-1][j]
                dp[i][j+a[i]]%=mod
    tmp*=2
    tmp%=mod
            
print(dp[n-1][s-1])
### BUGGY CODE ###

def main():

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

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a=[-_ for _ in a]
import heapq
heapq.heapify(a)
for i in range(m):
  temp=-heapq.heappop(a)
  heapq.heappush(a,-(temp//2))
  
print(-sum(a))
### BUGGY CODE ###

from collections import deque

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


def successors(x, y):
    locations = []
    # 下に行けるかの判定
    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))
    return locations


def bfs(initial, successors):
    # goal判定はなく、一番遠いところで返す
    frontier = deque()
    frontier.append((initial, None))
    # tuple
    explored = {initial}
    while len(frontier):
        current_node = frontier.pop()
        current_state = current_node[0]
        for child in successors(*current_state):
            if str(child) in [str(i) for i in explored]:
                continue
            explored.add(child)
            frontier.appendleft((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), successors)
            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 ###

#create date: 2020-09-19 21:14

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, x, m = na()
    ans = x
    l = [x]
    a = x
    for i in range(n-1):
        a = a**2
        a %= m
        if a == 0:
            ans += a
            print(ans)
            quit()
        if a in l:
            #print(a, l)
            j = l.index(a)
            r = i - j + 1
            res = sum(l[j:])
            k = ((n-i-1)%r)
            #print(k, n-i-1, r, l[j:(j+k)])
            ans += (n-i-1)//r * res + sum(l[j:(j+k)])
            break
        l.append(a)
        ans += a
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

#create date: 2020-09-19 21:14

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, x, m = na()
    ans = x
    l = [x]
    a = x
    for i in range(n-1):
        a = a**2
        a %= m
        if a == 0:
            ans += a
            print(ans)
            quit()
        if a in l:
            #print(a, l)
            j = l.index(a)
            r = i - j + 1
            res = sum(l[j:])
            k = ((n-i-1)%r)
            #print(k, n-i-1, r, l[j:(j+k)])
            ans += (n-i-1)//r * res + sum(l[j:(j+k)])
            break
        l.append(a)
        ans += a
    print(ans)

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

from collections import Counter
import math


def nC2(n):
    return math.factorial(n) // (math.factorial(n - 2) * math.factorial(2))


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

ac = dict(Counter(a))

ans = 0
for k, v in ac.items():
    if v < 2:
        ac[k] = (v, 0, 0)
    else:
        c = nC2(v)
        ans += c
        if v - 1 < 2:
            ac[k] = (v, c, 0)
        else:
            ac[k] = (v, c, nC2(v - 1))

for i in a:
    v = ac[i]
    if v[0] - 1 < 2:
        print(ans - v[1])
    else:
        print(ans - v[1] + v[2])

### FIXED CODE ###

from collections import Counter
from operator import mul
from functools import reduce


def nCr(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


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

ac = dict(Counter(a))

ans = 0
for k, v in ac.items():
    if v < 2:
        ac[k] = (v, 0, 0)
    else:
        c = nCr(v, 2)
        ans += c
        if v - 1 < 2:
            ac[k] = (v, c, 0)
        else:
            ac[k] = (v, c, nCr(v - 1, 2))

for i in a:
    v = ac[i]
    if v[0] - 1 < 2:
        print(ans - v[1])
    else:
        print(ans - v[1] + v[2])
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
S = input()
half_N = N//2
cand = [[] for _ in range(N-1)]
flag = True
for i in range(N):
    for j in range(1, N-i-1):
        if S[i] == S[i+j]:
            flag = False
            cand[i].append(i+j)
if flag:
    print(0)
    exit()

for length in range(1, N//2+1):
    flag = True
    new_cand = [[] for _ in range(N-1)]
    for i in range(N-length):
        tmp = []
        now_check = S[i+length]
        for c in cand[i]:
            if i + length >= c or c + length >= N:
                continue
            if S[c+length] == now_check:
                flag = False
                tmp.append(c)
        new_cand[i] = tmp
    cand = new_cand
    if flag:
        print(length)
        exit()
print(length+1)


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    N = int(input())
    S = input().strip()

    dp = [0] * N
    for i, s in enumerate(S):
        if i == 0:
            continue
        before_ans = dp[i-1]
        now_S = S[:i+1]
        tmp_ans = now_S[-(before_ans+1):i+1]
        # print(i, before_ans, tmp_ans)
        if tmp_ans in now_S[:-(before_ans+1)]:
            dp[i] = before_ans + 1
        else:
            dp[i] = before_ans
    print(dp[-1])


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

N=int(input())
A=[]

for i in range(N):
  A.append(int(input()))

for j in range(N):
  B=A[j]
  del A[j]
  print(max(A))
  A.insert(j,B)

### FIXED CODE ###

N=int(input())
A=[]

for i in range(N):
  A.append(int(input()))
B=sorted(A)
B=B[:len(B)-1]
C=[max(A)]*N
C[A.index(max(A))]=max(B)
for j in range(N):
  print(C[j])
### BUGGY CODE ###

N = int(input())
A = [int(n) for n in input().split()]
Q = int(input())

D = dict()
for a in A:
    if a not in D.keys():
        D[a] = 0
    D[a] += 1

for _ in range(Q):
    B, C = [int(n) for n in input().split()]
    
    if B in D.keys():
        if C not in D.keys():
            D[C] = 0
        D[C] += D[B]
        del D[B]

    ans = 0
    for k, v in D.items():
        ans += k * v
    print(ans)



### FIXED CODE ###

N = int(input())
A = [int(n) for n in input().split()]
Q = int(input())

D = dict()
for a in A:
    if a not in D.keys():
        D[a] = 0
    D[a] += 1

ans = 0
for k, v in D.items():
    ans += k * v
    
for _ in range(Q):
    B, C = [int(n) for n in input().split()]
    
    if B in D.keys():
        count = D[B]
        
        if C not in D.keys():
            D[C] = 0
        D[C] += count
        del D[B]
        
        ans += (C - B) * count

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

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

N,K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

answer = max(C)
for i in range(N):
  pos = P[i] - 1
  score = C[pos]
  score_list = [score]
  step = 1
  while pos!=i and step<K:
    pos = P[pos] - 1
    score += C[pos]
    score_list.append(score)
    step += 1
  score_max = max(score_list)
  if score_list[-1]>0 and step<K:
    loop = K//step
    amari = K%step
    for j in range(step):
      if j<amari:
        score_max = max(score_max, score_list[-1]*loop+score_list[j])
      else:
        score_max = max(score_max, score_list[-1]*(loop-1)+score_list[j])
  answer = max(answer,score_max)

print(answer)

### FIXED CODE ###

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

N,K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

answer = max(C)
for i in range(N):
  pos = P[i] - 1
  score = C[pos]
  score_list = [score]
  step = 1
  while pos!=i and step<K:
    pos = P[pos] - 1
    score += C[pos]
    score_list.append(score)
    step += 1
  score_max = max(score_list)
  if score_list[-1]>0 and step<K:
    loop = K//step
    amari = K%step
    for j in range(step):
      if j<amari:
        score_max = max(score_max, score_list[-1]*loop+score_list[j])
      else:
        score_max = max(score_max, score_list[-1]*(loop-1)+score_list[j])
  answer = max(answer,score_max)

print(answer)