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

N, M = map(int, input().split())
A, B = [], []
dic = {i:[] for i in range(1, N+1)}
for _ in range(M):
    a, b = map(int, input().split())
    dic[a].append(b)
    dic[b].append(a)

node = [float('inf')] * N
node[0] = 0 #1までの距離
route = [0]*N #ランプ置く部屋
rooms = [1] #次調べる部屋

for r1 in rooms:
    for r2 in dic[r1]:
        if node[r1-1] + 1 <= node[r2-1]:
            node[r2-1] = node[r1-1] + 1
            route[r2-1] = r1
            if not r2 in rooms:
                rooms.append(r2)
            try:
                dic[r2].remove(r1)
            except:
                continue

if float('inf') in node:
    print('No')
else:
    print('Yes')
    for i in route[1:]:
        print(i)


### FIXED CODE ###

N, M = map(int, input().split())
A, B = [], []
dic = {i:[] for i in range(1, N+1)}
for _ in range(M):
    a, b = map(int, input().split())
    dic[a].append(b)
    dic[b].append(a)

node = [float('inf')] * N
node[0] = 0 #1までの距離
route = [0]*N #ランプ置く部屋
rooms = [1] #次調べる部屋
st = {1}

for r1 in rooms:
    for r2 in dic[r1]:
        if node[r1-1] + 1 <= node[r2-1]:
            node[r2-1] = node[r1-1] + 1
            route[r2-1] = r1
            if not r2 in st:
                rooms.append(r2)
                st.add(r2)
            try:
                dic[r2].remove(r1)
            except:
                continue

if float('inf') in node:
    print('No')
else:
    print('Yes')
    for i in route[1:]:
        print(i)
### BUGGY CODE ###

L, R = map(int, input().split())
ans = []
for i in range(L, R):
    for j in range(L+1, R+1):
        ans.append((i*j)%2019)
print(min(ans))


### FIXED CODE ###

L, R = map(int, input().split())
def mod(L, R):
    ans = []
    for i in range(L, R):
        for j in range(L+1, R+1):
            if (i*j)%2019 == 0:
                return 0
            ans.append((i*j)%2019)
    return min(ans)
print(mod(L, R))
### BUGGY CODE ###

import sys
stdin=sys.stdin

ns = lambda:stdin.readline().rstrip()
ni = lambda:int(stdin.readline().rstrip())
nm = lambda:map(int,stdin.readline().split())
nl = lambda:list(map(int,stdin.readline().split()))

A,B,C,K=nm()
ans=0
for i in range(K):
    if(A>0):
        A-=1
        ans+=1
    elif(B>0):
        B-=1
    else:
        C-=1
        ans-=1

print(ans)

### FIXED CODE ###

import sys
stdin=sys.stdin

ns = lambda:stdin.readline().rstrip()
ni = lambda:int(stdin.readline().rstrip())
nm = lambda:map(int,stdin.readline().split())
nl = lambda:list(map(int,stdin.readline().split()))

A,B,C,K=nm()
ans=0

ans+=min(A,K)
K-=min(A,K)

if(K>0):
    K-=min(B,K)
if(K>0):
    ans-=min(C,K)

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

n = int(input())
monster = sorted(list(map(int, input().split())))
cnt = len(monster)
while cnt > 0:
    for i in range(len(monster)):
        for j in range(len(monster)):
            if i != j and monster[i] != 0:
                monster[j] %= monster[i]
                if monster[j] == 0:
                    cnt -= 1

print(max(monster))

### FIXED CODE ###

n = int(input())
monster = sorted(list(map(int, input().split())))

def gcd(a, b):
    while b:
	    a, b = b, a % b
    return a

for i in range(1,n):
    monster[i] = gcd(monster[0], monster[i])

print(min(monster))
### BUGGY CODE ###

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

S = input()

for _ in range(Q):
  l,r = map(int,input().split())
  print(S[l-1:r].count('AC'))

### FIXED CODE ###

N,Q = map(int,input().split())
 
S = [x for x in input()]

cnt =[0]
for a,b in zip(S,S[1:]):
  if a == 'A' and b == 'C':
    cnt.append(cnt[-1] + 1)    
  else:
    cnt.append(cnt[-1])

    
for _ in range(Q):
  l,r = map(int,input().split())
  print(cnt[r-1]-cnt[l-1])
### BUGGY CODE ###

from heapq import*
n,m,*p=map(int,open(0).read().split());a=p[:n];heapify(a)
for s,t in sorted([p[n:][i:i+2]for i in range(0,m*2,2)],key=lambda x:x[1])[::-1]:
    for i in range(s):
        tmp=heappop(a)
        if t>tmp:
            heappush(a,t)
        else:
            heappush(a,tmp)
            print(sum(a))
            exit()
print(sum(a))

### FIXED CODE ###

from heapq import*
n,m=map(int,input().split())
p=sorted(map(int,input().split()))
heapify(p)
q=sorted([list(map(int,input().split()))for i in range(m)],key=lambda x:x[1],reverse=1)

for s,t in q:
    for i in range(s):
        tmp=heappop(p)
        if t>tmp:
            heappush(p,t)
        else:
            heappush(p,tmp)
            print(sum(p))
            exit()
print(sum(p))
#    print(p,q)
### BUGGY CODE ###

from collections import deque

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

F=[[] for _ in range(N)]
B=[[] for _ in range(N)]
FM=[[0]*N for _ in range(N)]
BM=[[0]*N for _ in range(N)]


for i in range(M):
    a,b=map(int,input().split())
    F[a-1].append(b-1)
    F[b-1].append(a-1)
    FM[a-1][b-1]=1
    FM[b-1][a-1]=1

for i in range(K):
    a,b=map(int,input().split())
    B[a-1].append(b-1)
    B[b-1].append(a-1)
    BM[a-1][b-1]=1
    BM[b-1][a-1]=1

q=deque([])
cnt=[0]*N

for i in range(N):
    visited=[0]*N
    visited[i]=1
    for j in F[i]:
        if visited[j]==0:
            visited[j]=1
            q.append(j)
    while q:
        c=q.popleft()
        if FM[i][c]==1:
            for j in F[c]:
                if visited[j]==0:
                    visited[j]=1
                    q.append(j)
            continue
        if BM[i][c]==0:
            cnt[i]+=1
        for j in F[c]:
            if visited[j] == 0:
                visited[j]=1
                q.append(j)



for i in cnt:
    print(str(i),end=" ")


### FIXED CODE ###

from collections import deque

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

F=[[] for _ in range(N)]
B=[[] for _ in range(N)]


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

for i in range(K):
    a,b=map(int,input().split())
    B[a-1].append(b-1)
    B[b-1].append(a-1)

q=deque([])
G=[]
visited=[0]*N
group=[-1]*N
idx=0
for i in range(N):
    if visited[i]==1:continue
    visited[i]=1
    group[i]=idx
    q.append([i,[i]])
    while q:
        n,c=q.pop()
        for j in F[n]:
            if visited[j]==0:
                c.append(j)
                visited[j]=1
                group[j]=idx
                q.append([j,c])
    G.append(c)
    idx+=1

cnt=[0]*N
for g in G:
    for i in g:
        for b in B[i]:
            if  group[i]==group[b]:
                cnt[i]+=1

ans=[0]*N

for g in G:
    for i in g:
        ans[i]=len(g)-len(F[i])-cnt[i]-1

for i in ans:
    print(str(i),end=" ")
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

def gcd ( ax, ay):
    x = ax
    y = ay
    while (True):
        if x < y :
            tmp = x
            x = y
            y = tmp
        x=x %y
        if x == 0:
            return y
        elif x == 1:
            return 1

def check_pn(num):
    count = 0
    for i in range(2, num):
        if gcd(i, num) != 1:
            return False

    return True


n = int(input())
listdata = []
for i in range(n):
    listdata.append(int(input()))

count = 0
for data in listdata:
    count += check_pn(data)

print(count)



### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

def check_pn(num):
    if (num <2):
        return False
    elif (num==2):
        return True

    if (num%2 == 0):
        return False
    i = 3
    while (i <= num/i):
        if num % i == 0:
            return False
        i += 2

    return True


n = int(input())
listdata = []
for i in range(n):
    listdata.append(int(input()))

n=0
for data in listdata:
    ch = check_pn(data)
    n += ch

print (n)
### BUGGY CODE ###

N, M, Q = map(int, input().split())
tracks = [[] for i in range(N)]
for i in range(M):
    L, R = map(int, input().split())
    tracks[L-1].append(R-1)
    
for track in tracks: track.sort()

ans = [[None for j in range(N)] for i in range(N)]
for L in range(N):
    cur = 0
    tot = 0
    for R in range(L, N):
        while cur < len(tracks[L]) and tracks[L][cur] <= R:
            cur += 1
            tot += 1
        ans[L][R] = tot

for i in range(Q):
    p, q = map(int, input().split())
    print(sum(ans[i][q-1] for i in range(p-1, q)))


### FIXED CODE ###

N, M, Q = map(int, input().split())
tracks = [[] for i in range(N)]
for i in range(M):
    L, R = map(int, input().split())
    tracks[L-1].append(R-1)
    
for track in tracks: track.sort()

ans = [[None for j in range(N)] for i in range(N)]
for L in range(N):
    cur = 0
    tot = 0
    for R in range(L, N):
        while cur < len(tracks[L]) and tracks[L][cur] <= R:
            cur += 1
            tot += 1
        ans[L][R] = tot

dp =[[None for i in range(N)] for j in range(N)]
for i in range(Q):
    p, q = map(int, input().split())
    if dp[p-1][q-1] == None:
        dp[p-1][q-1] = sum(ans[i][q-1] for i in range(p-1, q))
    print(dp[p-1][q-1])
### BUGGY CODE ###

l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))
Sum = []
for i in range(l1[1] + 1):
    sum = 0
    for j in range(len(l2)):
        sum = sum + (i ^ l2[j])
    Sum.append(sum)
print(max(Sum))


### FIXED CODE ###

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

ans = 0
for i in range(40, -1, -1):
    j = 2 ** i
    count = len([1 for temp in a if temp&j > 0])
    if count < n - count and j <= k:
        k -= j
        count = n - count
    ans += j * count
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
count=0
F=0
B=1


while F<N:
    while True:

        XOR=0

        for l in A[F:B]:
            XOR=XOR ^ l

        if sum(A[F:B])==XOR:
            if B==N:
                count=count+(B-F)
                F+=1
                break
            else:
                B+=1

        else:
            count=count+(B-F-1)
            
            F+=1
            B=min(B-1,F+1)
            break


print(count)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
count=0
F=0
B=0
SUM=0



while F<N:
    while True:
        SUMtest=SUM+A[B]
        XORtest=SUM^A[B]

        if SUMtest==XORtest:
            if B==N-1:
                for i in range(F,N):
                    count=count+(N-i)
                F=N
                break
                
            else:
                B+=1
                SUM=SUMtest

        else:
            count=count+(B-F)
            SUM=SUM-A[F]
            F+=1
            break


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

from itertools import accumulate
def E(i, x):
    if i == 1:
        return 5 * x
    return (2 * i + 1) * x
N, X = map(int, input().split())
x = list(map(int, input().split()))
x.sort(key=None, reverse=True)
x = list(accumulate(x))
x.insert(0, 0)
energy = 9223372036854775807
for k in range(1, N + 1):
    cost = 0
    for i in range(1, N + 1):
        if i * k <= N:
            cost += E(i, x[i * k] - x[(i - 1) * k])
        else:
            cost += E(i, x[-1] - x[(i - 1) * k])
            break
    energy = min(energy, cost + (N + k) * X)
print(energy)


### FIXED CODE ###

from itertools import accumulate
def E(i, x):
    if i == 1:
        return 5 * x
    return (2 * i + 1) * x
N, X = map(int, input().split())
x = list(map(int, input().split()))
x.sort(key=None, reverse=True)
x = list(accumulate(x))
x.insert(0, 0)
energy = 9223372036854775807
for k in range(1, N + 1):
    cost = (N + k) * X
    for i in range(1, N + 1):
        if i * k <= N:
            cost += E(i, x[i * k] - x[(i - 1) * k])
        else:
            cost += E(i, x[-1] - x[(i - 1) * k])
            break
    if cost < energy:
        energy = cost
print(energy)
### BUGGY CODE ###

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
 



sys.setrecursionlimit(10 ** 6)

g = 0
#@lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1
    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



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

l = []
for _ in range(n - 1):
    a, b = li()
    g[a].append(b)
    g[b].append(a)


root = 1    
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)

### FIXED CODE ###

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
 



sys.setrecursionlimit(10 ** 6)

g = 0
@lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1
    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



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

l = []
for _ in range(n - 1):
    a, b = li()
    g[a].append(b)
    g[b].append(a)


root = 1    
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)
### BUGGY CODE ###

import sys
import math
from bisect import bisect_right
def main():
    N,M = map(int,input().split())
    Marray=[(0,0)] * M
    P={}
    for i in range(M):
        s = input().split()
        p=int(s[0])
        y=s[1]
        #print(s)
        if p in P.keys():
            P[p]+=y+","
        else:
            P[p]=y+","
        Marray[i]=(p,int(y))
        #print(P[p])
        
    for key in P:
        string=P[key]
        
       # print(str)
        sp=string.split(",")
        de=len(sp)-1
        del sp[de]
        #print(sp)
        tmp=sorted(sp,key=int)
        int_list=list(map(int,tmp))
        P[key]=int_list
        
        #print(P[key])
    
    for index,value in Marray:
        List=P[index]
        
        #print(list)
        result=bisect_right(List,value)
        result=str(result)
        index=str(index)
        index_zero = index.zfill(6)
        result_zero = result.zfill(6)
        print(index_zero,result_zero,sep='')



if __name__ == "__main__":
    main()







### FIXED CODE ###

import sys
import math
from bisect import bisect_right
def main():
    N,M = map(int,input().split())
    Marray=[(0,0)] * M
    P={}
    for i in range(M):
        s = input().split()
        p=int(s[0])
        y=s[1]
        #print(s)
        if p in P.keys():
            P[p].append(int(y))
        else:
            P[p]=[]
            P[p].append(int(y))
        Marray[i]=(p,int(y))
        #print(P[p])
        
    for key in P:
        #string=P[key]
        
       # print(str)
        #sp=string.split(",")
        #de=len(sp)-1
        #del sp[de]
        #print(sp)
        tmp=sorted(P[key],key=int)
        #int_list=list(map(int,tmp))
        P[key]=tmp
        
        #print(P[key])
    
    for index,value in Marray:
        List=P[index]
        
        #print(list)
        result=bisect_right(List,value)
        result=str(result)
        index=str(index)
        index_zero = index.zfill(6)
        result_zero = result.zfill(6)
        print(index_zero,result_zero,sep='')



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

N, M = map(int, input().split())
aLst = list(map(int, input().split()))
aLst.sort()
cdict = {}
for i in range(M):
    B, C = map(int, input().split())
    if C in cdict.keys():
        cdict[C] = cdict[C] + B
    else:
        cdict[C] = B

for i in aLst:
    if i in cdict.keys():
        cdict[i] = cdict[i] + 1
    else:
        cdict[i] = 1

sordC = sorted(cdict.items(), key=lambda x:x[0], reverse=True)
ans = 0
tmp = 0
for i in range(N):
    for j in range(sordC[i][1]):
        if tmp < N:
            ans += sordC[i][0]
            tmp += 1
        else:
            break
    if tmp >= N:
        break
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
aLst = list(map(int, input().split()))
aLst.sort()
cdict = {}
for i in range(M):
    B, C = map(int, input().split())
    if C in cdict.keys():
        cdict[C] = cdict[C] + B
    else:
        cdict[C] = B

for i in aLst:
    if i in cdict.keys():
        cdict[i] = cdict[i] + 1
    else:
        cdict[i] = 1

sordC = sorted(cdict.items(), key=lambda x:x[0], reverse=True)
ans = 0
tmp = 0
for i in range(N):
    for j in range(sordC[i][1]):
        if tmp < N:
            ans += sordC[i][0]
            tmp += 1
        else:
            break
    if tmp >= N:
        break
print(ans)
### BUGGY CODE ###

s = input()
t = input()

ls,lt = len(s),len(t)
if ls > lt:
    #短い方をsに固定
    s,t = t,s
    ls,lt = lt,ls
dp=[("",0,0)]
common_str_set = set([""])
max_len = 0
i_ans = 0
for i,c in enumerate(s):
    for common_str,j,l_dp in dp[:]:
        if max_len >= l_dp + min((ls - i,lt-j)):
            continue
        for k,ct in enumerate(t[j:],j):
            if c == ct and (common_str+c) not in common_str_set:
                dp.append((common_str+c,k+1,l_dp+1))
                common_str_set.add(common_str+c)
                if l_dp+1 > max_len:
                    max_len = l_dp+1
                    i_ans = len(dp)-1
                break
print(dp[i_ans][0])

### FIXED CODE ###

s = input()
t = input()

ls,lt = len(s),len(t)
dp = [[0]*(lt+1) for _ in [0]*(ls+1)]

for i,cs in enumerate(s,1):
    for j,ct in enumerate(t,1):
        if cs==ct:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

i = ls
j = lt
ans = ""
while i>0 and j>0:
    if s[i-1] == t[j-1]:
        ans += s[i-1]
        i -= 1
        j -= 1
    else:
        if dp[i-1][j] > dp[i][j-1]:
            i -=1
        else:
            j -=1
print(ans[::-1])
### BUGGY CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
dic = defaultdict(int)
n,k = readInts()
if k == 1:
    print(0)
elif n == 0:
    print(0)
elif n == 1:
    print(1)
else:
    while True:
        if dic[n]:
            break
        else:
            dic[n] = 1
            n = abs(n-k)
    m = float('inf')
    for k,v in dic.items():
        m = min(m,k)
    print(m)


### FIXED CODE ###

#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""
  
def main():
  n,k = map(int,input().split())
  WANTS = n//k
  EX = n - k*WANTS
  dic = {}
  mi_ = float("inf")
  mi_ = min(mi_,EX)
  
  while True:
    if str(EX) in dic:
      break
    else:
      dic[str(EX)] = 1
      EX = abs(EX-k)
      mi_ = min(mi_,EX)
  print(mi_)
  
  
if __name__ == '__main__':
  main()
### BUGGY CODE ###

import collections
import itertools
n = int(input())
v = list(map(int,input().split()))
#n = len(v)
c = collections.Counter(v).most_common()
if len(c) == 1:
    print(n//2)
    exit()
values, counts = zip(*c)
k = sorted(list(set(counts)),reverse=True)[:2]
pairs = []
for vcnt in c:
    val = vcnt[0]
    cnt = vcnt[1]
    #print(val,cnt)
    if cnt in k:
        pairs.append(val)
#print(pairs)
P = list(itertools.combinations(pairs,2))
#print(P)
ans = float('inf')
for pair in P:
    #print(pair)
    mc = pair[0]
    sc = pair[1]
    tmp = 0
    for i in range(n):
        if i % 2 == 0 and v[i] != mc:
            tmp += 1
        elif i % 2 == 1 and v[i] != sc:
            tmp += 1
    ttmp = 0
    for i in range(n):
        if i % 2 == 0 and v[i] != sc:
            ttmp += 1
        elif i % 2 == 1 and v[i] != mc:
            ttmp += 1

    ans = min(ans,min(tmp,ttmp))
    
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
v = list(map(int,input().split()))
o = Counter(v[::2]).most_common()
o.append((0,0))
e = Counter(v[1::2]).most_common()
e.append((0,0))
if o[0][0] == e[0][0]:
    ans = min(n - o[0][1] - e[1][1], n - o[1][1] - e[0][1])
else:
    ans = n - o[0][1] - e[0][1]
print(ans)
### BUGGY CODE ###

# -*- coding utf-8 -*-

a,b,x=map(int,input().split())
ans=0

for i in range(a,b+1):
    if i%x==0:
        ans+=1
    else:
        ans=ans

print(ans)


### FIXED CODE ###

# -*- coding utf-8 -*-

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

print(b//x - (a-1)//x  )
### BUGGY CODE ###

A,B,N = (map(int , input().split()))
max_ = 0
for x in range(1,N+1):
    max_ = max(max_,((A*x)//B - A * (x//B)))
print(max_)

### FIXED CODE ###

A,B,N = (map(int , input().split()))
min(B-1,N)
x = min(B-1,N)
print(((A*x)//B - A * (x//B)))
### BUGGY CODE ###

import numpy

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))
T.insert(0, 0)
T.append(sum(T))
V.insert(0, 0)
V.append(0)

Z = [0] * (len(T))
for i in range(len(T)-1):
    Z[i+1] = Z[i] + T[i+1]


def calc_speed(l, r, x, v):
    if x <= l:
        return v + (l-x)
    if l <= x <= r:
        return v
    if r <= x:
        return v + (x-r)


ans = 0
time_table = [0.5*i for i in range(sum(T)+1)]

for time in time_table:
    speed = 10**5
    for i in range(N+1):
        zero_speed = calc_speed(0, 0, time, 0)
        T_speed = calc_speed(sum(T), sum(T), time, 0)
        speed = min(speed, zero_speed, T_speed, calc_speed(Z[i], Z[i+1], time, V[i+1]))
    ans += 0.5 * speed

print(ans)


### FIXED CODE ###

"""
prd_xxx 様のコードを参考にさせていただきました。感謝です...！
https://beta.atcoder.jp/contests/abc076/submissions/1724160
"""

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))

maxv = [0]
# グラフを整える準備
for v, t in zip(V, T):
    # 転換地点では低い方に合わせる
    maxv[-1] = min(maxv[-1], v)
    for ti in range(t * 2):
        maxv.append(v)

T = len(maxv)
# 前からグラフを整える
for i in range(T - 1):
    maxv[i + 1] = min(maxv[i+1], maxv[i] + 0.5)

maxv[-1] = 0
# 後ろからグラフを整える
for i in reversed(range(T-1)):
    maxv[i] = min(maxv[i], maxv[i + 1] + 0.5)

ans = 0
# 台形計算
for i in range(T-1):
    ans += (maxv[i] + maxv[i+1]) * 0.25
print(ans)
### BUGGY CODE ###

import sys
LI = lambda: list(map(int, sys.stdin.readline().split()))
N, W = LI()
dp = [0] * (W + 1)
for weight, value in sorted(LI() for _ in range(N)):
    for w in range(W - weight, -1, -1):
        if dp[w + weight] < dp[w] + value:
            dp[w + weight] = dp[w] + value
print(dp[-1])

### FIXED CODE ###

import sys
LI = lambda: list(map(int, sys.stdin.readline().split()))
N, W = LI()
dp = [0] * (W + 1)
for weight, value in sorted(LI() for _ in range(N)):
    for w in range(W - weight, -1, -1):
        if dp[w + weight] < dp[w] + value:
            dp[w + weight] = dp[w] + value
print(dp[-1])