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

from sys import setrecursionlimit

setrecursionlimit(10**8)


def dp_solve(i, k, dp):
    if k == 0:
        if i == 0:
            return max(bx[i], cx[i])
        dp[i] = max(dp_solve(i-1, 1, dp)+ax[i], dp_solve(i-1, 2, dp)+ax[i])
    if k == 1:
        if i == 0:
            return max(ax[i], cx[i])
        dp[i] = max(dp_solve(i-1, 0, dp)+bx[i], dp_solve(i-1, 2, dp)+bx[i])
    if k == 2:
        if i == 0:
            return max(ax[i], bx[i])
        dp[i] = max(dp_solve(i-1, 0, dp)+cx[i], dp_solve(i-1, 1, dp)+cx[i])
    return dp[i]


if __name__ == "__main__":
    n = int(input())
    ax = []
    bx = []
    cx = []
    for i in range(n):
        a, b, c = map(int, input().split())
        ax.append(a)
        bx.append(b)
        cx.append(c)

    dp = [0]*n
    dp1 = dp_solve(n-1, 0, dp)
    dp = [0]*n
    dp2 = dp_solve(n-1, 1, dp)
    dp = [0]*n
    dp3 = dp_solve(n-1, 2, dp)
    print(max(dp1, dp2, dp3))


### FIXED CODE ###


def dp_solve(dp0, dp1, dp2, n):
    for i in range(1, n):
        dp0[i] = max(dp1[i-1], dp2[i-1])+ax[i]
        dp1[i] = max(dp0[i-1], dp2[i-1])+bx[i]
        dp2[i] = max(dp0[i-1], dp1[i-1])+cx[i]
    return max(dp0[-1], dp1[-1], dp2[-1])


if __name__ == "__main__":
    n = int(input())
    ax = []
    bx = []
    cx = []
    for i in range(n):
        a, b, c = map(int, input().split())
        ax.append(a)
        bx.append(b)
        cx.append(c)

    dp0 = [ax[0]]+[0]*(n-1)
    dp1 = [bx[0]]+[0]*(n-1)
    dp2 = [cx[0]]+[0]*(n-1)
    print(dp_solve(dp0, dp1, dp2, n))
### BUGGY CODE ###

import sys
n,m,k =map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

t = k
i = 0
asum = [0]* (n+1)
bsum = [0]* (m+1)
suma = 0
sumb = 0

for  i in range(n):
    suma += a[i]
    asum[i+1]= suma


for  i in range(m):
    sumb += b[i]
    bsum[i+1] = sumb

count = 1
ans = 0

for i in range(n+1):
    if ans < i :
        if asum[i] <= k:
            ans=i
    else:
        for j in range(ans-i,m+1,1):
            if asum[i] + bsum[j]<=k and i+j>ans:
                ans=i+j

print(min(ans,m+n))



### FIXED CODE ###

import sys
n,m,k =map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

t = k
i = 0
asum = [0]* (n+1)
bsum = [0]* (m+1)
suma = 0
sumb = 0

for  i in range(n):
    suma += a[i]
    asum[i+1]= suma


for  i in range(m):
    sumb += b[i]
    bsum[i+1] = sumb

count = 1
ans = 0

for i in range(n+1):
    if ans < i :
        if asum[i] <= k:
            ans=i
    else:
        for j in range(ans-i,m+1,1):
            if asum[i] + bsum[j]<=k:
                if i+j>ans:
                    ans=i+j
            else:
                break

print(min(ans,m+n))
### BUGGY CODE ###

n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
# 小さい順に調べていく
roads = []
for i in range(n-1):
    for j in range(i+1, n):
        roads.append((A[i][j], i, j))
roads = sorted(roads)

INF = 10**9*1
AD = [[INF]*n for _ in range(n)]
G = [[] for _ in range(n)]
edges = set()
from collections import deque
ok = True
ans = 0
for a, s, e in roads:
    # s to e
    q = deque([[s, 0]])
    visited = [INF] * n
    visited[s] = 0
    while q:
        node, dist = q.popleft()
        if node == e:
            # sからeにたどり着いて
            if dist == a:
                # あたえられた距離と同じならばOK
                break
            elif dist < a:
                # あたえられた距離より小さいならばaは最短距離じゃないNG
                ok = False
                break
        
        for nn, cost in G[node]:
            if dist+cost < visited[nn]:
                visited[nn] = dist+cost
                q.append([nn, dist+cost])
    else:
        # sからeにたどり着けなかったら最短距離確定
        AD[s][e] = a
        G[s].append((e, a))
        G[e].append((s, a))
        ans += a
    if not ok:
        break

print(ans if ok else -1)

### FIXED CODE ###

n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
INF = 10**9 + 1
dp = [[INF]*n for _ in range(n)]

# コスト登録
for i, line in enumerate(A):
    for j, a in enumerate(line):
        dp[i][j] = a

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        d = dp[i][j]
        if d < A[i][j]:
            ans = -1
            break
        else:
            for k in range(n):
                if k == i or k == j:
                    continue
                if dp[i][k] + dp[k][j] == d:
                    break
            else:
                ans += d
    if ans == -1:
        break
print(ans)
### BUGGY CODE ###

def main():
    n,m,k = map(int,input().split())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    ma = 0
    a2 = [0]
    b2 = [0]
    for i in range(len(a)):
        a2.append(a[i]+a2[i])
    for i in range(len(b)):
        b2.append(b[i]+b2[i])

    for i in range(len(a2)):
        #print(i)
        sum = a2[i]
        cnt = i
        if(a2[i]>k):
            break
        for j in range(len(b2)-1,0,-1):
            #print("i:{},j:{},b2[j]:{}".format(i,j,b2[j]))
            if(a2[i]+b2[j]<=k):
                cnt += j
                break
        ma = max(ma,cnt)
        #print("ma:",ma)

    print(ma)
            
main()

### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    hs = list(map(int, input().split()))

    dp = [float("inf")]*n
    dp[0] = 0

    for i in range(n):
        for j in range(1,k+1):
            if i+j < n:
                dp[i+j] = min(dp[i+j], dp[i]+abs(hs[i]-hs[i+j]))
    print(dp[-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

INF = 10**10

def main():
    n, k = map(int, input().split())
    hs = list(map(int, input().split()))

    dp = [INF]*n
    dp[0] = 0

    for i in range(1,n):
        from_ = max(i-k, 0)
        dp[i] = min(d + abs(hs[i]-h) for d, h in zip(dp[from_:i], hs[from_:i]))
    print(dp[-1])

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

while 1:
    n = input()
    if n==0: break
    s = [0 for i in range(13)]
    for i in range(n):
        s[input()/10] += 1
    for i in range(6):
        print s[i]
    print sum(s[6:])

### FIXED CODE ###

while 1:
    n = input()
    if n==0: break
    s = [0 for i in range(13)]
    for i in range(n):
        s[int(raw_input())/10] += 1
    for i in range(6):
        print s[i]
    print sum(s[6:])
### BUGGY CODE ###

#import sys
#input = sys.stdin.readline
n=int(input())
a=[int(i) for i in input().split()]

#print(a)
ans=0
if n==1:
  ans=1
else:
  for i in range(1,100000+1):
    cnt=0
    for j in a:
      if j==i or j==i-1 or j==i+1:
        cnt+=1
      if ans <= cnt:
        ans = cnt

print(ans)


### FIXED CODE ###

from collections import Counter

#tmp_list = [1, 1, 1, 1, 0, 1, 1]


n=int(input())
a=[int(i) for i in input().split()]
b=[i-1 for i in a]
c=[i+1 for i in a]
d=a+b+c

counter = Counter(d)

print(counter.most_common()[0][1])
### BUGGY CODE ###

import sys
 
# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())
 
def log(*args):
    print("DEBUG:", *args, file=sys.stderr)
 
def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]
 
def inv(x, MOD):
    return pow(x, MOD-2, MOD)
 
MOD = 10**9+7
 
debug = False
 
if debug:
    n = 50000
    A = list(range(n))
else:
    n,*A = get_all_int()
 
 
pow2 = [1] * 61
for i in range(1,61):
    pow2[i] = pow2[i-1] * 2

# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if pow2[i] & a != 0:
            bits[i] += 1

 
# log("bits:", bits)
 
ans = 0
 
for a in A:
    # a_bits = [ 1 if 2**i & a != 0 else 0 for i in range(60) ]
 
    for i in range(60):
        ans += 2**i * abs(bits[i] - (1 if 2**i & a != 0 else 0) *n)
 
    # a_dash = list(map(lambda a: a*(n-1), a_bits))
 
    # log("a_dash", a_dash)
 
    # bits_dash = [ bits[i] - a_bits[i] for i in range(60)]
    # log("bits_dash", bits_dash)
    # ans += sum( ( 2**i * abs(bits_dash[i]-2*a_dash[i])) for i in range(60) )
 
    # ans += sum( ( 2**i * abs(bits[i]-2*a_dash[i])) for i in range(60) )
 
    # for i in range(60):
    #     ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
    # log(a, ans)
 
print(ans//2 % MOD)

### FIXED CODE ###

import sys
import time

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

start = time.time()

MOD = 10**9+7

debug = False

if debug:
    n = 30 * 10000
    A = list(range(n))
else:
    n,*A = get_all_int()

# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)
# log("bits.", time.time() - start)

# ans = 0

ans = sum(( pow(2, i, MOD) * bits[i] * (n-bits[i]) for i in range(60))) % MOD

# for a in A:
#     # a_bits = [ 1 if 2**i & a != 0 else 0 for i in range(60) ]

#     for i in range(60):
#         ans += 2**i * abs(bits[i] - (1 if 2**i & a != 0 else 0) *n)

#     # a_dash = list(map(lambda a: a*(n-1), a_bits))

#     # log("a_dash", a_dash)

#     # bits_dash = [ bits[i] - a_bits[i] for i in range(60)]
#     # log("bits_dash", bits_dash)
#     # ans += sum( ( 2**i * abs(bits_dash[i]-2*a_dash[i])) for i in range(60) )

#     # ans += sum( ( 2**i * abs(bits[i]-2*a_dash[i])) for i in range(60) )

#     # for i in range(60):
#     #     ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
#     # log(a, ans)

# print(ans//2 % MOD)
print(ans)
# log("end.", time.time() - start)
### BUGGY CODE ###

def function(n):
  string = str(n)
  for i in range(len(string) - 1):
    if int(string[i]) - int(string[i + 1]) > 1:
      return i + 1
    elif int(string[i + 1]) - int(string[i]) > 1:
      return i
  return -1
 
k = int(input())
ans = []
n = 1
while len(ans) < k:
  m = function(n)
  if m == -1:
    ans.append(n)
    n += 1
  else:
    n = n + 10 ** (len(str(n)) - m - 1) - n % (10 ** (len(str(n)) - m - 1))
print(ans[-1])

### FIXED CODE ###

def function(n):
  string = str(n)
  for i in range(len(string) - 1):
    error = int(string[i]) - int(string[i + 1])
    if error > 1:
      return i + 1, error
    elif error < -1:
      return i, abs(error)
  return -1, 0
 
k = int(input())
ans = []
n = 1
while len(ans) < k:
  m, error = function(n)
  if m == -1:
    ans.append(n)
    n += 1
  else:
    n = n + (error - 1) * (10 ** (len(str(n)) - m - 1)) - n % (10 ** (len(str(n)) - m - 1))
print(ans[-1])
### BUGGY CODE ###

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

### FIXED CODE ###

a,b,k = map(int,input().split())
li = []
if 2 * k > b - a:
    for x in range(a,b+1):
        print(x)
else:
    for i in range(k):
        li.append(a + i)
    for i in range(k):
        li.append(b - i)
    for i in sorted(set(li)):
        print(i)
### BUGGY CODE ###

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

for i in range(0, n):
    for j in range(i + 1, n):
        if a[i] == a[j]:
            print("NO")
            exit()

print("YES")

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = {}
flag = 0

for i in A:
    if (ans.get(i) != None):
        flag = 1
        break
    else:
        ans[i] = 1

if (flag == 0):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

N, K = map(int, input().split())
Health = map(int, input().split())
temp = sorted(Health, reverse=True)
if K >= N:
    print(0)
else:
    for i in range(K):
        temp.pop(0)
    print(sum(temp))

### FIXED CODE ###

N, K = map(int, input().split())
Health = map(int, input().split())
temp = sorted(Health, reverse=True)
if K >= N:
    print(0)
else:
    print(sum(temp[K::]))
### BUGGY CODE ###

N = int(input())

s=0
for i in range(1,N+1):
    n = int(N/i)
    s += n*(i+i*n)/2
print(int(s))

### FIXED CODE ###

N = int(input())

s=0
for i in range(1,N+1):
    n = int(N/i)
    s += n*(i+i*n)/2
print(int(s))
### BUGGY CODE ###

import scipy.misc as scm

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

p = 10 ** 9 + 7
s = 0

for i in range(w-b):
    s += scm.comb(h+w-a-2-i, w-1-i, 1) * scm.comb(a-1+i, a-1, 1)

print(s%p)

### FIXED CODE ###

import scipy.misc as scm

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

p = 10**9 + 7
ans = 0

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(h+w)
rf = invfact(h+w, f)

for i in range(w-b):
    wi = b + i
    ans += (f[h-a+wi-1] * rf[h-a-1] % p * rf[wi] % p) * (f[a+w-wi-2] * rf[a-1] % p * rf[w-wi-1] % p) % p
    ans %= p 

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


import bisect

N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))

count = 0
for first in A:
    idx = bisect.bisect_right(B, first)
    seconds = B[idx:]

    for second in seconds:
        idx = bisect.bisect_right(C, second)
        thirds = C[idx:]

        count += len(thirds)

print(count)

### FIXED CODE ###


import bisect

N = int(input())
A = sorted(map(int, input().split()))
B = map(int, input().split())
C = sorted(map(int, input().split()))

ans = 0
for second in B:
    ai = bisect.bisect_left(A, second)
    ci = bisect.bisect_right(C, second)

    ans += (ai*(N-ci))

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

N,M=map(int,input().split())
A=[]
for I in range(M):
	x,y=map(int,input().split())
	A.append(list(range(x,y+1)))
F=set(A[0]).intersection(*A[1:])
print(len(F))

### FIXED CODE ###

N,M=map(int,input().split())
L=[]
R=[]
for I in range(M):
	x,y=map(int,input().split())
	L.append(x)
	R.append(y+1)
F=list(range(max(L),min(R)))
print(len(F))
### BUGGY CODE ###

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

if 0 in A:
    print(0)
    exit()

for i in range(N):
    ans *= A[i]
    if ans > pow(10,18):
        ans = -1

print(ans)

### FIXED CODE ###

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

limit = pow(10,18)

f = 0
for i in range(N):
    if A[i] != 0 and f == 0:
        ans *= A[i]
    elif A[i] != 0:
        pass
    else:
        print(0)
        exit()

    if ans > limit:
        f = 1

if f == 1:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

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


def main():
    S = input()
    l = len(S)
    amari =[int(S[-(i + 1) :]) % 2019 for i in range(l)]
    print(l - len(set(amari)) + amari.count(0))


if __name__ == "__main__":
    main()

### FIXED CODE ###

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


def main():
    S = input()[::-1] # 入力文字列を逆順で格納
    counts = [0] * 2019
    counts[0] = 1
    num, d = 0, 1

    for char in S:
        num = num + int(char) * d
        num = num % 2019
        d = d * 10
        d = d % 2019
        counts[num] += 1 #余りの数の番号のリストに+1していくことでカウント

    ans = 0
    for cnt in counts:
        ans += cnt * (cnt - 1) // 2
    print(ans)

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

# encoding: utf-8
N, M = list(map(int, input().split()))

# TLE
# Amod = [A for A in map(lambda x: int(x) % M , input().split())]
# ans = 0
# for l in range(len(Amod)):
#     acm = 0
#     for r in range(l, len(Amod)):
#         acm = (acm + Amod[r]) % M
#         if acm == 0: ans += 1

Asym = [0 for i in range(N)]
sym = 0
for i, A in enumerate(map(int, input().split())):
    sym = (sym + A) % M
    Asym[i] += sym
    
# ans = Asym.count(0)
# for sym in set(Asym):
#     cnt = Asym.count(sym)
#     ans +=  int(cnt * (cnt -  1) / 2)
    
# print(ans)
print(int(Asym.count(0) + sum([Asym.count(sym) * (Asym.count(sym) - 1) for sym in set(Asym)]) / 2))

# Acnt = [0 for i in range(M)]
# sym = 0
# for A in map(int, input().split()):
#     sym = (sym + A) % M
#     Acnt[sym] += 1

# print(int(Acnt[0] + sum([cnt * (cnt - 1) for cnt in Acnt]) / 2))


### FIXED CODE ###

# encoding: utf-8
N, M = list(map(int, input().split()))

d_sym = {}
sym = 0

# refresh

ans = 0
for A in map(int, input().split()):
    sym = (sym + A) % M
    #
    if sym == 0: ans += 1
    # 
    if str(sym) in d_sym.keys(): d_sym[str(sym)] += 1
    else: d_sym[str(sym)] = 1

print(int(ans + sum([val * (val - 1) / 2 for val in d_sym.values()])))
### BUGGY CODE ###

N = int(input())
lst = list(map(int,input().split()))
output = 1
for m in lst :
    output *= m
if output <= 1000000000000000000 :
    print(output)
else :
    print(-1)

### FIXED CODE ###

n = int(input())
ls = list(map(int, input().split()))
res = 1
if 0 in ls:
    print(0)
    quit()
for x in ls:
    res *= x
    if res > 10**18:
        print(-1)
        quit()
print(res)
### BUGGY CODE ###

import numpy as np
N, X, Y = map(int, input().split())
dist = [0] * (N + 1)
cnt = [0] * (N + 1)

INF = 10**10 + 9

# d = [[INF] * N for _ in range(N)]
d = [[abs(j - i) for j in range(N)] for i in range(N)]
d[X - 1][Y - 1] = 1
d[Y - 1][X - 1] = 1


def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


d = warshall_floyd(d)
count = np.bincount(np.array(d).flatten(), minlength=N)
count = count[1:] // 2
print(*count, sep='\n')


### FIXED CODE ###

N, X, Y = map(int, input().split())


def f(i, j):
    v1 = j - i
    v2 = abs(X - i) + 1 + abs(j - Y)
    v3 = abs(Y - i) + 1 + abs(j - X)
    return min(v1, v2, v3)


D = [0] * N
for i in range(1, N):
    for j in range(i + 1, N + 1):
        d = f(i, j)
        D[d] += 1

for d in D[1:]:
    print(d)
### BUGGY CODE ###

# AOTコンパイルテスト
import sys
import numpy as np
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()

def solve(dp,item):
    dptmp1 = np.copy(dp)
    dptmp2 = np.copy(dp)
    dptmp3 = np.copy(dp)
    for i in range(len(item)):
        dptmp3[item[i][0]:] = np.fmax(dptmp3[item[i][0]:], dptmp2[item[i][0]]+item[i][1])
        dptmp2[item[i][0]:] = np.fmax(dptmp2[item[i][0]:], dptmp1[item[i][0]]+item[i][1])
        dptmp1[item[i][0]:] = np.fmax(dptmp1[item[i][0]:], dp[item[i][0]]+item[i][1])
    return dptmp3


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
 
    cc = CC('my_module')
    cc.export('solve', 'i8[:](i8[:],i8[:,:])')(solve)
    cc.compile()
    exit()

def main():
    R, C, K = map(int, input().split())
    items = defaultdict(list)
    for _ in range(K):
        r, c, v = map(int, input().split())
        items[r-1].append([c-1, v])
    dp = np.zeros(C, dtype=int)
    for RR in range(R):
        if items[RR]==[]:
          continue
        items[RR].sort(key=lambda x: x[0])
        dp=solve(dp,np.array(items[RR],dtype=int))
    print(dp[-1])

main()

### FIXED CODE ###

import sys
import numpy as np
from collections import defaultdict
from numba import njit
def input(): return sys.stdin.readline().rstrip()

@njit
def koushin(dp,item):
    dptmp1 = np.copy(dp)
    dptmp2 = np.copy(dp)
    dptmp3 = np.copy(dp)
    for i in range(len(item)):
        dptmp3[item[i][0]:] = np.fmax(dptmp3[item[i][0]:], dptmp2[item[i][0]]+item[i][1])
        dptmp2[item[i][0]:] = np.fmax(dptmp2[item[i][0]:], dptmp1[item[i][0]]+item[i][1])
        dptmp1[item[i][0]:] = np.fmax(dptmp1[item[i][0]:], dp[item[i][0]]+item[i][1])
    return dptmp3

def main():
    R, C, K = map(int, input().split())
    items = defaultdict(list)
    for _ in range(K):
        r, c, v = map(int, input().split())
        items[r-1].append([c-1, v])
    dp = np.zeros(C, dtype=int)
    for RR in range(R):
        if items[RR]==[]:
          continue
        items[RR].sort(key=lambda x: x[0])
        dp=koushin(dp,np.array(items[RR],dtype=int))
    print(dp[-1])


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

i = list(map(int, input().split()))
A = i[0]
B = i[1]
N = i[2]
a = []
for x in range(1, N+1):
  s = A * x // B
  t = A * (x // B)
  a.append(s-t)
b = max(a)
print(b)


### FIXED CODE ###

i = list(map(int, input().split()))
A = i[0]
B = i[1]
N = i[2]
if N < B-1:
    print(A * N // B)
else:
    print(A * (B-1) // B)
### BUGGY CODE ###

'''
包除原理
すべての条件を満たしている
2^{N-1}から「どれかの条件を満たしていない」を引けば良い
i番目の条件を満たしていない確率はかんたんに計算できる
Sに属していいないやつが全て条件を満たしていない確率については
Sに対応する辺が全て白となる確率を考えれば良い
'''
from collections import deque
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
M=int(input())
u=[0 for i in range(M)]
v=[0 for i in range(M)]
for i in range(M):
    u[i],v[i]=map(int,input().split())
    u[i]-=1;v[i]-=1
root=[set() for i in range(M)]
for i in range(M):
    q=deque([u[i]])
    parents=[-1 for i in range(N)]
    reached=[0 for i in range(N)]
    while(len(q)>0):
        r=q.popleft()
        reached[r]=1
        for p in G[r]:
            if reached[p]==1:
                continue
            parents[p]=r
            q.append(p)
    x=v[i]
    while(1):
        if parents[x]==-1:
            break
        s=min(x,parents[x])
        t=max(x,parents[x])
        root[i].add((s,t))
        x=parents[x]
#print(root)
ans=0
def cnt(x):
    ans=0
    for i in range(M):
        if x|(2**i)==x:
            ans+=1
    return ans
q=deque([])
q.append(0)
S=[set() for i in range(2**M)]
reached=[0 for i in range(2**M)]
while(len(q)>0):
    i=q.popleft()
    for j in range(M):
        if i&(2**j)==0:
            S[i|(2**j)]=S[i]|{k for k in root[j]}
            if reached[i|(2**j)]==0:
                q.append(i|(2**j))
                reached[i|(2**j)]=1
    ans+=(-1)**(cnt(i))*2**(N-len(S[i])-1)
print(ans)



### FIXED CODE ###

'''
包除原理
すべての条件を満たしている
2^{N-1}から「どれかの条件を満たしていない」を引けば良い
i番目の条件を満たしていない確率はかんたんに計算できる
Sに属していいないやつが全て条件を満たしていない確率については
Sに対応する辺が全て白となる確率を考えれば良い
'''
from collections import deque
N=int(input())
G=[[] for i in range(N)]
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
edges=dict()
for i in range(N-1):
    a[i],b[i]=map(int,input().split())
    a[i]-=1;b[i]-=1
    G[a[i]].append(b[i])
    G[b[i]].append(a[i])
    edges[(min(a[i],b[i]),max(a[i],b[i]))]=i
M=int(input())
u=[0 for i in range(M)]
v=[0 for i in range(M)]
for i in range(M):
    u[i],v[i]=map(int,input().split())
    u[i]-=1;v[i]-=1
root=[0 for i in range(M)]
for i in range(M):
    q=deque([u[i]])
    parents=[-1 for i in range(N)]
    reached=[0 for i in range(N)]
    while(len(q)>0):
        r=q.popleft()
        reached[r]=1
        for p in G[r]:
            if reached[p]==1:
                continue
            parents[p]=r
            q.append(p)
    x=v[i]
    while(1):
        if parents[x]==-1:
            break
        s=min(x,parents[x])
        t=max(x,parents[x])
        root[i]+=2**edges[(s,t)]
        x=parents[x]
ans=0
def cnt(x):
    ans=0
    for i in range(M):
        if x|(2**i)==x:
            ans+=1
    return ans
q=deque([])
q.append(0)
S=[0 for i in range(2**M)]
reached=[0 for i in range(2**M)]
while(len(q)>0):
    i=q.popleft()
    for j in range(M):
        if i&(2**j)==0:
            S[i|(2**j)]=S[i]|root[j]
            if reached[i|(2**j)]==0:
                q.append(i|(2**j))
                reached[i|(2**j)]=1
    ans+=(-1)**(cnt(i))*2**(N-bin(S[i]).count("1")-1)
print(ans)