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

n = int(input())
s = input()
pass_list = list(map(lambda x: str(x).zfill(3), range(1000)))
res = 0

for p in pass_list:
    
    ptr = 0
    one = False
    two = False
    three = False
    
    for i in range(len(s)):
        if(s[i] == p[0]):
            ptr = i
            one = True
            break
    
    for i in range(ptr+1, len(s)):
        if(s[i] == p[1]):
            ptr = i
            two = True
            break
    
    for i in range(ptr+1, len(s)):
        if(s[i] == p[2]):
            ptr = i
            three = True
            break
    
    if(one and two and three): res += 1

print(res)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

n = int(input())
s = input()
pass_list = list(map(lambda x: str(x).zfill(3), range(1000)))
res = 0

for p in pass_list:
    
    ptr = 0
    one = False
    two = False
    three = False
    
    for i in range(len(s)):
        if(s[i] == p[0]):
            ptr = i
            one = True
            break
    
    for i in range(ptr+1, len(s)):
        if(s[i] == p[1]):
            ptr = i
            two = True
            break
    
    for i in range(ptr+1, len(s)):
        if(s[i] == p[2]):
            ptr = i
            three = True
            break
    
    if(one and two and three): res += 1

print(res)
### BUGGY CODE ###

import numpy as np
n,m = map(int,input().split())

p = [0] * (n+1)
s = [0] * (n+1)

s[1]=1

a = [0] * m
b = [0] * m


for i in range(m):
    a[i],b[i] = map(int,input().split())

for i in range(1,n+1):
    t=False
    for j in range(1,n+1):
        if s[j] == i:
            for k in range(m):
                if a[k]==j and p[b[k]] == 0:
                    p[b[k]]=a[k]
                    s[b[k]]=i+1
                    t=True

                if b[k]==j and p[a[k]]==0:
                    p[a[k]]=b[k]
                    s[a[k]]=i+1
                    t=True
    if t==False:
        break
    
if 0 in p[2:]:
    print('No')
else:
    print('Yes')
    for q in p[2:]:
        print(q)


### FIXED CODE ###

import numpy as np
n,m = map(int,input().split())

p = [0 for i in range(n+1)]
q = list()
q2 = list()

g=[[] for i in range(n+1)]

for i in range(m):
    a,b = map(int,input().split())
    g[a].append(b)
    g[b].append(a)


q2.append(1)

while 1:
    q=q2
    q2=[]

    while len(q):
        v = q.pop()
        
        for nv in g[v]:
            if p[nv] == 0:
                p[nv]=v
                g[nv].remove(v)
                q2.append(nv)
    if len(q2)==0:
        break

if 0 in p[2:]:
    print('No')
else:
    print('Yes')
    for q in p[2:]:
        print(q)
### BUGGY CODE ###

N, M = map(int, input().split())
ES = []
D = {}

*parent, = range(M)
def root(x):
    if x == parent[x]:
        return x
    parent[x] = y = root(parent[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py

E = {}
for i in range(M):
    p, q, c = map(int, input().split()); p -= 1; q -= 1
    ES.append((p, q, c))
    if (p, c) in D:
        unite(D[p, c], i)
    D[p, c] = i
    E.setdefault(p, set()).add(c)
    if (q, c) in D:
        unite(D[q, c], i)
    D[q, c] = i
    E.setdefault(q, set()).add(c)
#P = [[] for i in range(M)]
P = {}
for i in range(M):
    j = root(i)
    p, q, c = ES[i]
    s = P.setdefault(j, set())
    s.add(p); s.add(q)

from collections import deque
que = deque([(0, 0, 0)])
INF = 10**18
dist = [INF]*N
dist[0] = 0
gdist = [INF]*M

while que:
    cost, v, t = que.popleft()
    if t:
        # edge
        if gdist[v] < cost or v not in P:
            continue
        for w in P[v]:
            if cost < dist[w]:
                dist[w] = cost
                que.appendleft((cost, w, 0))
    else:
        # node
        if dist[v] < cost or v not in E:
            continue
        for c in E[v]:
            w = root(D[v, c])
            if cost + 1 < gdist[w]:
                gdist[w] = cost + 1
                que.append((cost + 1, w, 1))

print(dist[N-1] if dist[N-1] < INF else -1)


### FIXED CODE ###

N, M = map(int, input().split())
ES = []
D = {}

*parent, = range(M)
def root(x):
    if x == parent[x]:
        return x
    parent[x] = y = root(parent[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py

E = {}
for i in range(M):
    p, q, c = map(int, input().split()); p -= 1; q -= 1
    ES.append((p, q, c))
    if (p, c) in D:
        unite(D[p, c], i)
    D[p, c] = i
    E.setdefault(p, set()).add(c)
    if (q, c) in D:
        unite(D[q, c], i)
    D[q, c] = i
    E.setdefault(q, set()).add(c)
#P = [[] for i in range(M)]
P = {}
for i in range(M):
    j = root(i)
    p, q, c = ES[i]
    s = P.setdefault(j, set())
    s.add(p); s.add(q)

from collections import deque
que = deque([(0, 0, 0)])
INF = 10**18
dist = [INF]*N
dist[0] = 0
gdist = [INF]*M

while que:
    cost, v, t = que.popleft()
    if t:
        # edge
        if gdist[v] < cost or v not in P:
            continue
        for w in P[v]:
            if cost + 1 < dist[w]:
                dist[w] = cost + 1
                que.append((cost + 1, w, 0))
    else:
        # node
        if dist[v] < cost or v not in E:
            continue
        for c in E[v]:
            w = root(D[v, c])
            if cost < gdist[w]:
                gdist[w] = cost
                que.appendleft((cost, w, 1))

print(dist[N-1] if dist[N-1] < INF else -1)
### BUGGY CODE ###

h, w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
diff = [[0]*(w+1) for i in range(h+1)]

for i in range(h):
    for j in range(w):
        diff[i][j] = abs(a[i][j] - b[i][j])

n = 80 * 80 + 1
dp = [[False]*n for i in range(h*w)]
dp[0][diff[0][0]] = True

for i in range(h):
    for j in range(w):
        for cnt in range(n):
            if dp[i*w + j][cnt]:

                if i+1 < h and cnt + diff[i+1][j] < 80 * 80 + 1:
                    dp[i*w+w + j][cnt + diff[i+1][j]] = True
                if i+1 < h:
                    dp[i*w+w + j][abs(cnt - diff[i+1][j])] = True

                if j+1 < w and cnt + diff[i][j+1] < 80 * 80 + 1:
                    dp[i*w + j+1][cnt + diff[i][j+1]] = True
                if j+1 < w:
                    dp[i*w + j+1][abs(cnt - diff[i][j+1])] = True 

for i, boo in enumerate(dp[w*h - 1][0:81]):
    if boo:
        print(i)
        exit()
print(a[10*9])

### FIXED CODE ###

import sys
input = sys.stdin.readline


h, w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]

diff = [[0]*(w) for i in range(h)]
for i in range(h):
    for j in range(w):
        diff[i][j] = abs(a[i][j] - b[i][j])

dp = [0] * (h*w)
dp[0] |= 1 << (13000 + diff[0][0])
dp[0] |= 1 << (13000 - diff[0][0])

for k in range(h*w):
    i = k // w
    j = k % w
    if i+1 < h:
        tmp1 = diff[i+1][j]
        dp[k + w] |= dp[k] << tmp1
        dp[k + w] |= dp[k] >> tmp1       
    if j+1 < w:
        tmp2 = diff[i][j+1]
        dp[k + 1] |= dp[k] << tmp2
        dp[k + 1] |= dp[k] >> tmp2


ans = 10**9
for i in range(81):
    if dp[w*h - 1] >> 13000 + i & 1:
        ans = min(ans, i)
for i in range(81):
    if dp[w*h - 1] >> 13000 - i & 1:
        ans = min(ans, i) 
print(ans)
### BUGGY CODE ###

N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

minimumCost = [0] * N

for currentIndex in range(1, N):
  minimumCost[currentIndex] = min(minimumCost[previousIndex] + abs(h[currentIndex] - h[previousIndex]) for previousIndex in range(max(currentIndex - K, 0), currentIndex))

print(minimumCost[N - 1])


### FIXED CODE ###

def solve():
  N, K = [int(i) for i in input().split()]
  H = [int(i) for i in input().split()]
  dp = [0] * N

  for i in range(1, N):
    dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i - K, 0), i))

  return dp[N - 1]

print(solve())
### BUGGY CODE ###

n=int(input())
s=input()*2
for a in['SS','SW','WS','WW']:
    for i in range(1,n+1):
        f=a[i]+s[i]
        if f=='So'or'Wx'==f:
            a+=a[i-1]
        else:
            a+=a[i-1].translate({83:87,87:83})
    if a[:2]==a[n:]:
        print(a[:n])
        break
else:
    print(-1)

### FIXED CODE ###

n=int(input())
s=input()*2
for a in['SS','SW','WS','WW']:
    for i in range(1,n+1):
        f=a[i]+s[i]
        if f=='So'or'Wx'==f:
            a+=a[i-1]
        else:
            a+=a[i-1].translate({83:87,87:83})
    if a[:2]==a[n:]:
        print(a[:n])
        break
else:
    print(-1)
### BUGGY CODE ###

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

def binary_search_left(list,target):
    '''
    配列に対してある数nを配列のソート順を崩さないように挿入するためのindexを返す関数。
    同一の数が配列に複数含まれていた場合は最も小さいindexを返す。
    '''
    result = -1
    left = 0
    right = len(list) - 1

    while left <= right:
        center = (left + right)//2
        if list[center] == target:          # 一致した場合
            if list[center - 1] == target:  # -> その一つ前も一致した場合、rightをcenterにしてもう一周
                right = center
            else:                           # -> その一つ前は一致しない場合、一番左で一致したということでcenterを返す
                return center
        elif list[center] < target:
            left = center + 1
        elif list[center] > target:
            right = center - 1
    return left                             # 一致したらcenterを返すが（上記）、なければleftのインデックスを返す
  
L_list = sorted(L_list)

ans = 0
for a_index in range(0, N):
    for b_index in range(a_index+1, N):
        a = L_list[a_index]
        b = L_list[b_index]
        c_right_index = binary_search_left(L_list, a+b)
        if c_right_index > b_index:
            ans += c_right_index - b_index - 1
        else:
            pass

print(ans)

### FIXED CODE ###

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

import bisect

L_list = sorted(L_list)
 
ans = 0
for a_index in range(0, N):
    for b_index in range(a_index+1, N):
        a = L_list[a_index]
        b = L_list[b_index]
        c_right_index = bisect.bisect_left(L_list, a+b)
        if c_right_index > b_index:
            ans += c_right_index - b_index - 1
        else:
            pass

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

a,b,c,d=map(int,input().split())
X=a*c
for i in range(a,b+1) :
  for j in range(c,d+1) :
    X=max(X,i*j)
print(X)

### FIXED CODE ###

a,b,c,d=map(int,input().split())
print(max(a*c,a*d,b*c,b*d))
### BUGGY CODE ###

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

for i in range(m):
  b, c = map(int,input().split())
  for j in range(b):
    a[a.index(min(a))] = max(c, min(a))

print(sum(a))

### FIXED CODE ###

#5618213
n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)
  
for b,c in bc:
  a.extend([c]*b)
  if len(a) > n*2:
    break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

import sys
n, m = map(int, input().split())
br = [int(sys.stdin.readline()) for i in range(m)]

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

dp[0] = 1
if 1 not in br:
    dp[1] = 1
for i in range(2, n + 1):
    if i in br:
        continue
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] = dp[i] % (10 ** 9 + 7)
print(dp[n])



### FIXED CODE ###

n, m = map(int, input().split())
p = {int(input()) for _ in range(m)}
s = 10 ** 9 + 7

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
if 1 in p:
    dp[1] = 0

for i in range(2, n+1):
    if i in p:
        continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % s

print(dp[-1])
### BUGGY CODE ###

# 15:20
n = int(input())
s = [0] * n
ans = 0
for i in range(n):
    t = sorted(input())
    ans += s.count(t)
    s[i] = t
print(ans)

### FIXED CODE ###

# 15:20 -16:08 giveup
# 21:45 -22:33 review
from collections import Counter

# 3
# acornistnt
# peanutbomb
# constraint
n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
# s is ['acinnorstt', 'abbemnoptu', 'acinnorstt']
counter = Counter(s)
# counter is Counter({'acinnorstt': 2, 'abbemnoptu': 1})
# counter.values() is dict_values([3, 2])
ans = sum(x*(x-1)//2 for x in counter.values())
print(ans)
### BUGGY CODE ###

data = []

def maxsearchex(n):
	maxInt = 0
	for i in range(len(data)):
		if i != n:
			if maxInt < data[i]:
				maxInt = data[i]
	print(maxInt)

i = input()

for n in range(int(i)):
	data.append(int(input()))

for i in range(len(data)):
	maxsearchex(i)



### FIXED CODE ###

import copy

data = []
i = int(input())

data = [int(input()) for _n in range(i)]
maxInt = max(data)
data2 = copy.copy(data)
data2.remove(maxInt)
max2Int = max(data2)
for n in range(i):
	if maxInt != data[n]:
		print(maxInt)
	else:
		print(max2Int)
### BUGGY CODE ###

n=int(input())
v=list(map(int, input().split()))
c=list(map(int, input().split()))
ans=0

for i in range(2 ** n):
    total = 0
    for j in range(n):  
        if ((i >> j) & 1):  
            total+=v[j]-c[j]        
    ans=max(ans,total)    
print(ans)

### FIXED CODE ###

n=int(input())
v=list(map(int, input().split()))
c=list(map(int, input().split()))
ans=0

for i in range(n):
    if (v[i]>c[i]):  
        ans+=v[i]-c[i]        
 
print(ans)
### BUGGY CODE ###

n = int(input())
t, a = map(int, input().split())
for i in range(1, n):
    x, y = map(int, input().split())
    i = 1
    c, d = x, y
    while c < t or d< a:
        c = x * i
        d = y * i
        i += 1
    t, a = c, d
print(t + a)

### FIXED CODE ###

n = int(input())
t, a = map(int, input().split())
for i in range(1, n):
    x, y = map(int, input().split())
    i = max(t // x, a // y)
    c, d = x, y
    while c < t or d< a:
        c = x * i
        d = y * i
        i += 1
    t, a = c, d
print(t + a)
### BUGGY CODE ###

n, q = map(int, input().split())
s = str(input())

for i in range(q):
  l, r = map(int, input().split()) 
  sp = s[l-1:r]
  print(sp.count('AC'))


### FIXED CODE ###

n, q = map(int, input().split())
s = str(input())

cum = [0]*n
current = 0

flag = 0

for i in range(1, len(s)):
  if s[i-1] == 'A' and s[i] =='C':
    current += 1
  cum[i] = current

for i in range(q):
  l, r = map(int, input().split())
  print(cum[r-1]-cum[l-1])
### BUGGY CODE ###

import heapq
from collections import deque
n,m = map(int,input().split())
g = [[] for i in range(n)]
h = [[] for i in range(n)]
for i in range(m):
  x,y = map(int,input().split())
  x-=1;y-=1
  g[x].append(y)
  h[y].append(x)
hukasa = [0]*n
MIN = float("inf")
for i in range(n):
  MIN = min(MIN,len(h[i]))
def dfs(x,y):
  for k in g[x]:
    if hukasa[k] < y+1:
      heapq.heappush(que,[-(y+1),k])
for i in range(n):
  if MIN == len(h[i]):
    que = [[0,i]]
    heapq.heapify(que)
    while que:
      y,x = heapq.heappop(que)
      if hukasa[x] < -y:
        hukasa[x] = -y
      dfs(x,-y)
print(max(hukasa))

### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
g = [[] for i in range(n)]
h = [[] for i in range(n)]
for i in range(m):
  x,y = map(int,input().split())
  x-=1;y-=1
  g[x].append(y)
  h[y].append(x)
topo = []
hukasa = [0] * n
hairu = [0]*n
que = deque([])
for i in range(n):
  hairu[i] = len(h[i])
  if hairu[i] == 0:
    topo.append(i)
    que.append(i)
def dfs(x):
  for i in g[x]:
    hairu[i]-=1
    if hairu[i] == 0:
      topo.append(i)
      que.append(i)
while que:
  x = que.popleft()
  dfs(x)
def dfs2(x):
  for i in g[x]:
    hukasa[i] = max(hukasa[i],hukasa[x]+1)
for i in topo:
  dfs2(i)
print(max(hukasa))
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

# @njit
def solve(N, costX, costY):
    ans = [INF] * (N + 1)

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = np.minimum(cx, cy).sum()
        ans[M] = min(ans[M], cost)

    return ans

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    XYP.sort(key=lambda xyp: xyp[2], reverse=False)

    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]

    def calcCost(AP, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    ans = solve(N, costX, costY)
    print(*ans, sep='\n')

sol()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6) #for deep recursion

N, Q = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(N-1)]
counts = [0] * N
operations = [list(map(int, input().split())) for _ in range(Q)]

counts = [0] * N
for op in operations:
    p, x = op
    counts[p-1] += x
    
all_connected_vertices = {i: [] for i in range(1, 1+N)}
for a, b in edges:
    all_connected_vertices[a].append(b)
    all_connected_vertices[b].append(a)
    
def get_connected_vertices(v):
    res = all_connected_vertices[v]
    return list(set(res))    
    
visited_vertices = [] 
def dfs(point):
    visited_vertices.append(point)
    connected_vertices = get_connected_vertices(point)
    children = [v for v in connected_vertices if v not in visited_vertices]
    for c in children:
        counts[c-1] += counts[point-1]
        dfs(c)
    
dfs(1)
res = ""
for c in counts:
    res += " " + str(c)
    
print(res[1:])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6) #for deep recursion

N, Q = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

counts = [0] * N
for op in operations:
    p, x = op
    counts[p-1] += x
    
all_connected_vertices = {i: [] for i in range(1, 1+N)}
for a, b in edges:
    all_connected_vertices[a].append(b)
    all_connected_vertices[b].append(a)
    
def dfs(point, pre):
    connected_vertices = all_connected_vertices[point]
    for c in connected_vertices:
        if c == pre:
            continue
        counts[c-1] += counts[point-1]
        dfs(c, point)
    
dfs(1, -1)
    
print(*counts)
### BUGGY CODE ###

import sys

input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

branch = [[] for _ in range(N)]
res = [0,]*N
root = [None]*N
t = 0

def search(p):
    global t
    root[p-1] = t
    t += 1
    for q in branch[p-1]:
        if root[q-1] != None:
            continue
        search(q)
    t -= 1

def dfs(p, x):
    res[p-1] += x
    for q in branch[p-1]:
        if root[q-1] < root[p-1]:
            continue
        dfs(q, x)


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

search(1)

for _ in range(Q):
    p, x = map(int, input().split())
    dfs(p, x)


print(*res)

### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

branch = [[] for _ in range(N)] # [[]]*N だと参照渡しになってしまう
X = [0,]*N
root = [None]*N
t = 0

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

for _ in range(Q):
    p, x = map(int, input().split())
    X[p-1] += x


def search(p):
    global t
    root[p-1] = t
    t += 1
    for q in branch[p-1]:
        if root[q-1] != None:
            continue
        X[q - 1] += X[p - 1]
        search(q)
    t -= 1



search(1)
print(*X)
### BUGGY CODE ###

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

if n < b:
    print((a*n)//b)
    exit()

num = n//b
ans = 0

for i in range(1,num+1):
    num2 = i*b-1
    #print(num2)
    temp = (a*num2)//b - a * (num2//b)
    ans = max(temp,ans)



print(max(ans,(a*n)//b - a * (n//b)))


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():

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

    if n < b:
        print((a*n)//b)
        exit()

    num = n//b

    ans = (a*(b-1))//b
    print(max(ans,(a*n)//b - a * (n//b)))

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

import sys
def main():
    N=int(sys.stdin.readline())
    A=list(map(int,sys.stdin.readline().split()))
    x=1
    for a in A:x*=a
    if x>10**18:x=-1
    print(x)
if __name__=='__main__':main()

### FIXED CODE ###

import sys
def v():
    N=int(sys.stdin.readline())
    A=list(map(int,sys.stdin.readline().split()))
    if A.count(0)>0:return 0
    else:
        A=list(filter(lambda x:x>1,A))
        x=1
        for a in A:
            x*=a
            if x>10**18:
                x=-1
                break
        return x
def main():print(v())
if __name__=='__main__':main()
### BUGGY CODE ###

import numpy as np

N, K = map(int, input().split())
P = np.int64(input().split()) - 1
C = np.int64(input().split())

vis = np.zeros(N, dtype=bool)
ans = np.zeros(N, dtype=int) - 10 ** 10
for root in range(N):
    if vis[root]:
        continue
    vis[root] = True

    cycle = [root]
    costs = [C[root]]
    u = P[root]
    while u != root:
        cycle.append(u)
        costs.append(C[u])
        u = P[u]

    # print('-' * 10)
    # print(cycle)
    # print(costs)

    L = len(cycle)
    S = sum(costs)
    for i, v in enumerate(cycle):
        cnt = 0
        for step in range(1, min(L, K) + 1):
            cnt += costs[(i + step) % L]
            val1 = cnt
            val2 = cnt + (K - step) // L * S
            ans[v] = max(ans[v], val1, val2)

print(ans.max().item())



### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [p - 1 for p in P]
C = list(map(int, input().split()))

vis = [False] * N
ans = [-float('inf')] * N

for root in range(N):
    if vis[root]:
        continue
    vis[root] = True

    cycle = [root]
    costs = [C[root]]
    u = P[root]
    vis[u] = True
    while u != root:
        cycle.append(u)
        costs.append(C[u])
        u = P[u]
        vis[u] = True

    # print('-' * 10)
    # print(cycle)
    # print(costs)

    L = len(cycle)
    S = sum(costs)
    for i, v in enumerate(cycle):
        cnt = 0
        for step in range(1, min(L, K) + 1):
            cnt += costs[(i + step) % L]
            val1 = cnt
            val2 = cnt + (K - step) // L * S
            ans[v] = max(ans[v], val1, val2)

print(max(ans))