Harryxun/sft_time huggingface dataset:
### BUGGY 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)]

SA=[[0]*W for i in range(H)]

for i in range(H):
    for j in range(W):
        SA[i][j]=abs(A[i][j]-B[i][j])

DP=[[[] for i in range(W)] for i in range(H)]

DP[0][0]=[SA[0][0]]

def next(i,j):
    RET=[]
    if i+j<=6400:
        RET.append(i+j)
    RET.append(abs(i-j))

    return RET

for i in range(H):
    for j in range(W):
        for k in set(DP[i][j]):
            if i+1<H:
                DP[i+1][j].extend(next(k,SA[i+1][j]))
            if j+1<W:
                DP[i][j+1].extend(next(k,SA[i][j+1]))
                
print(min(DP[-1][-1]))

### 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)]

SA=[[0]*W for i in range(H)]

for i in range(H):
    for j in range(W):
        SA[i][j]=abs(A[i][j]-B[i][j])

DP=[[0 for i in range(W)] for j in range(H)]

DP[0][0]=1<<(H+W)*80+SA[0][0]

for i in range(H):
    for j in range(W):
        tempbit=DP[i][j]
        if i+1<H:
            DP[i+1][j]|=tempbit<<SA[i+1][j]
            DP[i+1][j]|=tempbit>>SA[i+1][j]

        if j+1<W:
            DP[i][j+1]|=tempbit<<SA[i][j+1]
            DP[i][j+1]|=tempbit>>SA[i][j+1]

ANS=1<<30
for i in range((H+W)*160+1):
    if 1<<i & DP[-1][-1]!=0:
        ANS=min(ANS,abs(i-(H+W)*80))

print(ANS)
### BUGGY CODE ###

s = input()
 
s = s[::-1]
 
dp = [[0 for _ in range(13)] for __ in range(len(s)+1)]
 
l = len(s)
 
 
if s[0] == '?':
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(s[0])] = 1
 
m = 1
MOD = 10**9 +7
 
for i in range(1,len(s)):
    m = m*10 % 13
 
    if s[i] == '?':
        for k in range(13):
            for j in range(10):
                dp[i][(j*m+k)%13] += dp[i-1][k]
                dp[i][k] % MOD
    else:
        for k in range(13):
            dp[i][(int(s[i])*m + k) %13] += dp[i-1][k]
            dp[i][k] % MOD
 
print(dp[len(s)-1][5] % MOD )

### FIXED CODE ###

s = input()
 
s = s[::-1]
 
dp = [[0 for _ in range(13)] for __ in range(len(s)+1)]
 
l = len(s)
 
 
if s[0] == '?':
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(s[0])] = 1
 
m = 1
MOD = 10**9 +7
 
for i in range(1,len(s)):
    m = m*10 % 13
 
    if s[i] == '?':
        for k in range(13):
            for j in range(10):
                dp[i][(j*m+k)%13] += dp[i-1][k]
                dp[i][k] %= MOD
    else:
        for k in range(13):
            dp[i][(int(s[i])*m + k) %13] += dp[i-1][k]
            dp[i][k] %= MOD
 
print(dp[len(s)-1][5] % MOD )
### BUGGY CODE ###

import heapq

h, w = map(int, input().split())
i0, j0 = map(lambda x: int(x) - 1, input().split())
i1, j1 = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]
inf = 10**10
D = [[inf] * w for i in range(h)]
D[i0][j0] = 0
Q = [(0, (i0, j0))]
heapq.heapify(Q)
while Q:
    _, (i, j) = heapq.heappop(Q)
    for di in range(-2, 3):
        for dj in range(-2, 3):
            ii, jj = i + di, j + dj
            if 0 <= ii < h and 0 <= jj < w and S[ii][jj] == ".":
                nex = int(abs(di) + abs(dj) != 1)
                if D[i][j] + nex < D[ii][jj]:
                    D[ii][jj] = D[i][j] + nex
                    heapq.heappush(Q, (D[ii][jj], (ii, jj)))
if D[i1][j1] >= inf:
    print(-1)
else:
    print(D[i1][j1])


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
i0, j0 = map(lambda x: int(x) - 1, input().split())
i1, j1 = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]
D = [[-1] * w for i in range(h)]
Q = deque([(i0, j0, 0)])
while Q:
    i, j, cnt = Q.popleft()
    if D[i][j] != -1:
        continue
    D[i][j] = cnt
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if 0 <= i + di < h and 0 <= j + \
                    dj < w and S[i + di][j + dj] == "." and D[i + di][j + dj] == -1:
                if abs(di) + abs(dj) == 1:
                    Q.appendleft((i + di, j + dj, cnt))
                else:
                    Q.append((i + di, j + dj, cnt + 1))
print(D[i1][j1])
### BUGGY CODE ###

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

import sys
import math

def main():
    input = sys.stdin.readline
    N = int(input())

    result = 0
    small_ok_flag = False
    ok_flag = False
    for n in range(1,N+1):
        root_n = int(math.sqrt(n)) + 1
        if n < 3:
            print(0) 
            continue
        for i in range(1,root_n):
            for j in range(1,root_n):
                for k in range(i,root_n):
                    if i*i + j*j + k*k + i*j + i*k + j*k > n:
                        break
                    if i*i + j*j + k*k + i*j + i*k + j*k == n:
                        if i == j and j == k:
                            result += 1
                        elif i == j or j == k or i == k:
                            result += 3
                        else:
                            result += 6
                        print(result)
                        result = 0
                        ok_flag = True
                        break
                if ok_flag:
                    break
            if ok_flag:
                break

        if not ok_flag:
            print(0)
        ok_flag = False
        
                        

    return


if __name__ == '__main__':
    main()

### FIXED CODE ###

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

import sys
import math

def main():
    input = sys.stdin.readline
    N = int(input())

    result = 0
    ans_list = [0]*(N+1)
    root_n =int(math.sqrt(N))+1

    for i in range(1,root_n):
        for j in range(1,root_n):
            for k in range(1,root_n):
                f = i**2+j**2+k**2+i*j+i*k+j*k
                if f <= N:
                    ans_list[f] += 1 
    
    for i in range(1,N+1):
        print(ans_list[i])
        
                        

    return


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

import numpy as np
from sys import stdin

n, m = map(int, stdin.readline().split())
a = [int(num) for num in stdin.readline().split()]

cnt_dict = {}
mtr = [stdin.readline().rstrip().split() for _ in range(m)]
for row in mtr:
    cnt_dict.setdefault(int(row[1]), 0)
    cnt_dict[int(row[1])] += int(row[0])
for a_ in a:
    cnt_dict.setdefault(a_, 0)
    cnt_dict[a_] += 1

cnt_dict = sorted(cnt_dict.items(), key=lambda x: -x[0])

cnt = 0
ans = 0

for (k, v) in cnt_dict:
    v_ = np.min([v, n - cnt])
    ans += v_ * k
    cnt += v_
    if cnt == n:
        break


print(ans)


### FIXED CODE ###

from sys import stdin

n, m = map(int, stdin.readline().split())
a = [int(num) for num in stdin.readline().split()]

cnt_list = [(a[i], 1) for i in range(n)]
for i in range(m):
    b, c = map(int, stdin.readline().split())
    cnt_list.append((c, b))

cnt_list.sort()
cnt_list.reverse()

cnt = n
ans = 0

for (k, v) in cnt_list:
    acc_v = min(v, cnt)
    ans += k * acc_v
    cnt -= acc_v


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

import itertools

N = int(input())
S = input()

ss = set()

for i in range(N):
    for j in range(i + 1, N):
        for k in range(j + 1, N):
            ss.add(S[i] + S[j] + S[k])
print(len(ss))


### FIXED CODE ###

N = int(input())
S = input()

count = 0
for p in range(1000):
    v = format(p, '03')
    found = False
    pos1 = S.find(v[0])
    if pos1 == -1:
        continue
    pos2 = S[pos1 + 1:].find(v[1])
    if pos2 == -1:
        continue
    pos3 = S[pos1 + pos2 + 2:].find(v[2])
    if pos3 == -1:
        continue
    count += 1

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

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

is_distinct = False
for i in range(n):
  for j in range(i+1, n):
    if A[i] == A[j]:
      is_distinct = True
      break

if is_distinct:
  print('NO')
else:
  print('YES')

### FIXED CODE ###

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

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

#import math
#import itertools
import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
#MOD = 10 ** 9 + 7
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    ban=[]
    h,w=INTM()
    for i in range(h):
        s=STR()
        ban.append(s)
    left =np.zeros((h,w),dtype=np.int16)
    right=np.zeros((h,w),dtype=np.int16)
    up   =np.zeros((h,w),dtype=np.int16)
    down =np.zeros((h,w),dtype=np.int16)
    #print(up)
    for i1 in range(h):
        for i2 in range(w):
            i3=(w-1)-i2
            i4=(h-1)-i1
            if ban[i1][i2]=="#":
                left[i1][i2]=0
                up[i1][i2]=0
            else:
                if i1==0:
                    up[i1][i2]=1
                else:
                    up[i1][i2]=up[i1-1][i2]+1

                if i2==0:
                    left[i1][i2]=1
                else:
                    left[i1][i2]=left[i1][i2-1]+1
            if ban[i1][i3]=="#":
                right[i1][i3]=0
            else:
                if i2==0:
                    right[i1][i3]=1
                else:
                    right[i1][i3]=right[i1][i3+1]+1    

            if ban[i4][i2]=="#":
                down[i4][i2]=0
            else:
                if i1==0:
                    down[i4][i2]=1
                else:
                    down[i4][i2]=down[i4+1][i2]+1
    anslist=down+up+right+left
    ans=0
    for i in anslist:
        ans=max(ans,max(i))
    print(ans-3)


if __name__=='__main__':
    do()

### FIXED CODE ###

#import math
#import itertools
import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
#MOD = 10 ** 9 + 7
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    h,w=INTM()
    ban=np.zeros((h,w),dtype=np.int16)
    for i in range(h):
        s=STR()
        for i1 in range(len(s)):
            if s[i1]==".":
                ban[i][i1]=1

    left =np.zeros((h,w),dtype=np.int16)
    right=np.zeros((h,w),dtype=np.int16)
    up   =np.zeros((h,w),dtype=np.int16)
    down =np.zeros((h,w),dtype=np.int16)
    #print(up)
    for i in range(w):
        i2=w-1-i
        if i==0:
            left[:,i]=ban[:,i]
            right[:,i2]=ban[:,i2]
        else:
            left[:,i]=ban[:,i]*(left[:,i-1]+1)
            right[:,i2]=ban[:,i2]*(right[:,i2+1]+1)
    
    for i in range(h):
        i2=h-1-i
        if i==0:
            up[i,:]=ban[i,:]
            down[i2,:]=ban[i2,:]
        else:
            up[i,:]=ban[i,:]*(up[i-1,:]+1)
            down[i2,:]=ban[i2,:]*(down[i2+1,:]+1)
    

    anslist=down+up+right+left
    ans=0
    for i in anslist:
        ans=max(ans,max(i))
    print(ans-3)


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

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

ans = 1

for i in num_list:
    ans *= i

if ans > 10**18:
    print('-1')
else:
    print(ans)

### FIXED CODE ###

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

ans = 1

if 0 in num_list:
    print(0)
else:
    for i in num_list:
        ans *= i
        if ans > 10**18:
            print('-1')
            break

    if ans<= 10**18:
        print(ans)
### BUGGY CODE ###

import numpy as np

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

possible = True
ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            if k in (i, j):
                continue
            if A[i][j] < A[i][k] + A[k][j]:
                continue
            elif A[i][j] == A[i][k] + A[k][j]:
                break
            else:
                possible = False
                break
        else:
            ans += A[i][j]
print(ans if possible else -1)

### FIXED CODE ###

def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()
### BUGGY CODE ###

n,k=map(int,input().split())
ans=0
num=[n]


def func(x):
    x=abs(x-k)
    while(x not in num):
        num.append(x)
        x=abs(x-k)
    return min(num)
if n==0 or k==1:
    print(0)
else:
    print(func(n))


### FIXED CODE ###

n,k=map(int,input().split())
ans=0
if n==0 or k==1:
    print(0)
else:
    s=n%k
    b=k-n%k
    print(min(s,b))
### BUGGY CODE ###

t,a,k = map(int,input().split())

for _ in range(k):
  if t:
    t-=1
  elif a:
    a-=1
print(t,a)

### FIXED CODE ###

t,a,k = map(int,input().split())
 
t = t-k
if t<0:
  a += t
  t = 0
if a<0:
  a = 0
print(t,a)
### BUGGY CODE ###

n = int(input())
list = list(map(int,input().split()))
list2=[]

for i in range(n):
	k = list[i]
	list2.append(list.count(k)-1)
su = sum(list2)/2
for i in range(n):
	print(int(su-list2[i]))

### FIXED CODE ###

n = int(input())
list = list(map(int,input().split()))
di = {}
for i in range(n):
	k = list[i]
	if k not in di:
		di[k]=1
	else:
		di[k]+=1
"""
list_del=[]
for key in di.keys():
	if di[key]==1:
		list_del.append(key)
for i in range(len(list_del)):
	di.pop(list_del[i])
"""
	
su=0
for valu in di.values():
	su += valu*(valu-1)/2
	
for i in range(n):
	k = list[i]
	l = di[k]
	su_ch = su
	su_ch -= l*(l-1)/2
	su_ch += (l-1)*(l-2)/2
	print(int(su_ch))
### BUGGY CODE ###

from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())

    d = Counter(A)
    # print(d)

    for i in range(Q):
        ans = 0
        b, c = map(int, input().split())
        if b in d.keys():
            d[c] += d[b]
            d[b] = 0
        for k, v in d.items():
            ans += k * v
        # print(d)
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())

    d = Counter(A)
    # print(d)
    ans = sum(A)

    for i in range(Q):
        b, c = map(int, input().split())
        if d[b] != 0:
            ans -= d[b] * b
            ans -= d[c] * c
            d[c] += d[b]
            d[b] = 0
            ans += d[c] * c

        print(ans)


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

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))



N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    temp=[0 for i in range(N)]
    for j in many_int():
        temp[N-j-1]=1
    treasures.append("".join(list(map(str,temp))))

max_index=2**N
INF=10**15

dp=[INF for i in range(max_index)]
dp[0]=0

for i in range(max_index):
    for j in range(M):
        new_i = int(bin(int(treasures[j],2) | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

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



### FIXED CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]
    check={}

    for i in range(M):
        mon,_ =two_int()
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        
        if sums in check:
            if check[sums] > mon:
                check[sums]=mon
        else:
            check[sums]=mon
            
    for k,v in check.items():
        key_list.append(v)
        treasures.append(k)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp[0]=0
    M=len(key_list)

    for i in range(max_index-1):
        for j in range(M):
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            dp[new_i] = min(dp[new_i], cost) 
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()
### BUGGY CODE ###

p=[1 for i in range(1001)]
p[0]=0
p[1]=0
for i in range(2,1001):
    if p[i]==1:
        for j in range(2,1001):
            if i*j<=1000:
                p[i*j]=0
#print(p[:25])
Prime=[]
for i in range(1001):
    if p[i]==1:
        Prime.append(i)
#print(Prime)
#print(len(Prime))
N=int(input())
L=list(map(int,input().split()))

def gcd(a,b):
    if b>a:
        a,b=b,a
    while a%b!=0:
        a,b=b,a%b
    return b
    
X=L[0]
for i in range(1,N):
    X=gcd(X,L[i])
    if X==1:
        break
if X>1:
    print("not coprime")
    exit()
        
D={}
for i in L:
    I=i
    for j in Prime:
        if I%j==0:
            if j not in D:
                D[j]=1
            else:
                print("setwise coprime")
                exit()
            while I%j==0:
                I//=j
    if I!=1:
        if I not in D:
            D[I]=1
        else:
            print("setwise coprime")
            exit()
#print(D)

print("pairwise coprime")

### FIXED CODE ###

import time
A=time.time()
p=[1 for i in range(1001)]
p[0]=0
p[1]=0
for i in range(2,1001):
    if p[i]==1:
        for j in range(2,1001):
            if i*j<=1000:
                p[i*j]=0
#print(p[:25])
Prime=[]
for i in range(1001):
    if p[i]==1:
        Prime.append(i)

#print(Prime)
#print(len(Prime))
N=int(input())
L=list(map(int,input().split()))

def gcd(a,b):
    if b>a:
        a,b=b,a
    while a%b!=0:
        a,b=b,a%b
    return b
    
X=L[0]
for i in range(1,N):
    X=gcd(X,L[i])
    if X==1:
        break
if X>1:
    print("not coprime")
    exit()
        
D={}

for I in L:
    B=time.time()
    if B-A>1.9:
        print("pairwise coprime")
        exit()
    for j in Prime:
        if I%j==0:
            if j not in D:
                D[j]=1
            else:
                print("setwise coprime")
                exit()
            while I%j==0:
                I//=j
    if I!=1:
        if I not in D:
            D[I]=1
        else:
            print("setwise coprime")
            exit()
#print(D)

print("pairwise coprime")
### BUGGY CODE ###

from heapq import heapify,heapreplace
n,m = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(m)]

A.sort()
heapify(A)

BC = sorted(BC,key=lambda x:(x[1]),reverse=True)
for b,c in BC:
    if c<A[0]:
        break
    for i in range(b):
        if A[0]>c:
            break
        heapreplace(A,c)
    
#print(A)
print(sum(A))


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    A = list(map(int,input().split()))
    BC = [list(map(int,input().split())) for _ in range(m)]

    BC = sorted(BC,key=lambda x:(x[1]),reverse=True)
    append_list = []
    for b,c in BC:
        if len(append_list)>=n:
            break
        append_list+=[c]*b
    A+=append_list
    A.sort(reverse=True)
    print(sum(A[:n]))
if __name__=='__main__':
    main()
### BUGGY CODE ###

def main():
    h,w=map(int,input().split())
    L=80*(h+w)+1
    a=[list(map(int,input().split())) for i in range(h)]
    b=[list(map(int,input().split())) for i in range(h)]


    x=[[abs(a[i][j]-b[i][j]) for j in range(w)] for i in range(h)]
    
    p=x[0][0]
    L=p+80*(h+w-2)+1
    
    state=[[[0 for k in range(L)] for j in range(w)] for i in range(h)]


    state[0][0][p]=1

    for j in range(1,w):
        p=x[0][j]
        for k in range(L):
            if state[0][j-1][k]==1:
                state[0][j][k+p]=1
                state[0][j][abs(k-p)]=1

    for i in range(1,h):
        p=x[i][0]
        for k in range(L):
            if state[i-1][0][k]==1:
                state[i][0][k+p]=1
                state[i][0][abs(k-p)]=1

    for i in range(1,h):
        for j in range(1,w):
            p=x[i][j]
            for k in range(L):
                if state[i-1][j][k]==1 or state[i][j-1][k]==1:
                    state[i][j][k+p],state[i][j][abs(k-p)]=1,1



    for k in range(L):
        if state[h-1][w-1][k]==1:
            print(k)
            break
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    h,w=map(int,input().split())
    L=80*(h+w)+1
    a=[list(map(int,input().split())) for i in range(h)]
    b=[list(map(int,input().split())) for i in range(h)]


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

    L=12800
    
    state=[[0]*w for _ in range(h)]
    delta=x[0][0]
    state[0][0]=(2**L>>delta)|(2**L<<delta)

    for j in range(1,w):
        delta=x[0][j]
        state[0][j]=(state[0][j-1]>>delta)|(state[0][j-1]<<delta)

    for i in range(1,h):
        delta=x[i][0]
        state[i][0]=(state[i-1][0]>>delta)|(state[i-1][0]<<delta)

    for i in range(1,h):
        for j in range(1,w):
            delta=x[i][j]
            state[i][j]=(state[i][j-1]>>delta)|(state[i][j-1]<<delta)
            state[i][j]|=(state[i-1][j]>>delta)|(state[i-1][j]<<delta)

    
    ans = 10**9
    for i in range(L*2):
        if state[h-1][w-1] & 1:
            ans = min(ans,abs(i-L))
        state[h-1][w-1]>>=1
    print(ans)



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

import math

A, B, N = map(int, input().split(' '))
ans = 0
for x in range(min(B, N + 1)):
    res = math.floor((A * x) / B) - A * (math.floor(x / B))
    ans = max(res, ans)
print(int(ans))


### FIXED CODE ###

import math

A, B, N = map(int, input().split(' '))
ans = 0
x = min(B, N + 1) - 1
ans = math.floor((A * x) / B) - A * (math.floor(x / B))
print(int(ans))
### BUGGY CODE ###

n = int(input())
btn = []
checked = []
flag = True

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

def find(n):
  global btn, checked
  j = 1
  count = 0
  for i in range(n):
    if btn[j - 1] == 2:
      count += 1
      return count
    elif j - 1 in checked:
      return -1
    else:
      checked.append(j - 1)
      j = btn[j - 1]
      count += 1
  return -1

print(find(n))

### FIXED CODE ###

n = int(input())
btn = []
checked = set()

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

def find(n):
  global btn, checked
  j = 1
  for i in range(n):
    if btn[j - 1] == 2:
      # count += 1
      return len(checked) + 1
    elif j - 1 in checked:
      return -1
    else:
      checked.add(j - 1)
      j = btn[j - 1]
  return -1

print(find(n))