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

h,n=map(int,input().split())
MAX_NUM=9999999999
ab=[]
for _ in range(n):
    ab.append(list(map(int,input().split())))
dp=[MAX_NUM for _ in range(h+1)]
dp[0]=0

for i in range(h):
    if(dp[i]==MAX_NUM):
        continue

    for j in range(n):
        a,b=ab[j]
        if(i+a<h):
            dp[i+a]=min(dp[i+a],dp[i]+b)
        else:
            dp[-1]=min(dp[-1],dp[i]+b)
print(dp[-1])



### FIXED CODE ###

h,n=map(int,input().split())
ab=[]
for _ in range(n):
    ab.append(list(map(int,input().split())))
max_a=max([a for a,b in ab])
dp=[0 for _ in range(h+max_a)]

for i in range(1,len(dp)):
    dp[i]=min(dp[i-a]+b for a,b in ab)
print(min(dp[h:]))


#
# MAX_NUM=9999999999
# ab=[]
# for _ in range(n):
#     ab.append(list(map(int,input().split())))
# dp=[MAX_NUM for _ in range(h+1)]
# dp[0]=0
#
# for i in range(h):
#     if(dp[i]!=MAX_NUM):
#         for j in range(n):
#             a,b=ab[j]
#             ind = i+a if i+a<h else -1
#             dp[ind]=min(dp[ind],dp[i]+b)
# print(dp[-1])
### BUGGY CODE ###

def main():
    nvertices, nedges, s = map(int, input().split())
    E = []
    for i in range(nedges):
        u, v, w = map(int, input().split())
        E.append((u, v, w))

    INF = 1000000000
    d = [INF] * nvertices
    d[s] = 0
    for i in range(nvertices - 1):
        for u, v, w in E:
            if d[u] + w < d[v]:
                d[v] = d[u] + w

    for val in d:
        if val >= INF:
            print("INF")
        else:
            print(val)


main()

### FIXED CODE ###

import heapq


def main():
    nvertices, nedges, s = map(int, input().split())
    adj = [[] for i in range(nvertices)]
    for i in range(nedges):
        u, v, w = map(int, input().split())
        adj[u].append((v, w))

    INF = float('inf')
    costs = [INF] * nvertices
    costs[s] = 0
    que = [(0, s)]
    for i in range(1, nvertices):
        que.append((INF, 1))
    cnt = 0
    while que:
        cost, u = heapq.heappop(que)
        if cost > costs[u]:
            continue
        costs[u] = cost
        for v, w in adj[u]:
            if costs[v] > costs[u] + w:
                costs[v] = costs[u] + w
                heapq.heappush(que, (costs[v], v))
        cnt += 1
        if cnt == nvertices:
            break

    for i in range(nvertices):
        print(costs[i] if costs[i] < INF else "INF")


main()
### BUGGY CODE ###

from collections import deque
import copy

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

V = deque(map(int,input().split(" ")))

def search(N,K,V,score,a,b):
    if a+b < min(N,K):
        Vb = copy.copy(V)
        scoreA = copy.copy(score)
        scoreB=copy.copy(score)
        scoreA.append(V.popleft())
        A = search(N,K,V,scoreA,a+1,b)
        scoreB.append(Vb.pop())
        B = search(N,K,Vb,scoreB,a,b+1)
    score=sorted(score)
    counter = 0
    while(counter < K-a-b):
        if len(score)== 0:
            break;
        if score[0]<0:
            score.pop(0)
            counter +=1
        else:
            break;
    ans = sum(score)
    if a+b < min(N,K):
        return max(0,ans,A,B)
    else:
        return max(0,ans)

score = []
a = 0
b= 0
ans = search(N,K,V,score,a,b)
print(ans)

### FIXED CODE ###

from collections import deque

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

V = deque(map(int,input().split(" ")))

def search(N,K,V,score):
    ans = 0
    for i in range(min(N,K)+1):
        for j in range(min(N,K)-i+1):
            score = []
            for a in range(i):#do operation A
                score.append(V[a])
            for b in range(j):#do operation B
                score.append(V[len(V)-b-1])
            score=sorted(score)
            counter = 0

            while(counter < K-i-j):#do operation C,D
                if len(score)== 0:
                    break;
                if score[0]<0:
                    score.pop(0)
                    counter +=1
                else:
                    break;   
            ans = max(ans,sum(score))

    return ans

score = []
ans = search(N,K,V,score)
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
ans = 0

for i in range(1, k+1):
    for j in range(1, k+1):
        for k in range(1, k+1):
            ans += gcd(i, j, k)

print(ans)

### FIXED CODE ###

from math import gcd
 
n = int(input())
 
ans = 0
 
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      ans += gcd(gcd(i,j),k)
      
print(ans)
### BUGGY CODE ###

def parent(n):
    return (n+1)/2-1

def left(n):
    return (n+1)*2-1

def right(n):
    return (n+1)*2

def max_heapify(A, i):
    l = left(i)
    r = right(i)
    largest = i
    if l < len(A) and A[largest] < A[l]:
        largest = l
    if r < len(A) and A[largest] < A[r]:
        largest = r

    if largest != i:
        A[largest],A[i] = A[i],A[largest]
        max_heapify(A,largest)

def build_max_heap(A):
    for i in reversed(range((len(A)-1)/2+1)):
        max_heapify(A,i)

def up_heap(A,i):
    p = parent(i)
    if p >= 0 and A[p] < A[i]:
        A[p],A[i] = A[i],A[p]
        up_heap(A,p)

def extract_max(A):
    ret = A[0]
    A[0] = A[len(A)-1]
    del A[len(A)-1]
    max_heapify(A,0)
    return ret


heap = []
while True:
    c = raw_input()
    if c[0] == 'i':
        n = int(c[7:])
        heap.append(n)
        up_heap(heap,len(heap)-1)
    elif c[:2] == 'ex':
        print extract_max(heap)
    else:
        break

### FIXED CODE ###

from sys import stdin

def max_heapify(A, i):
    l = i*2
    r = i*2+1
    largest = i
    if l <= A[0] and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r <= A[0] and A[largest] < A[r]:
        largest = r

    if largest != i:
        A[largest],A[i] = A[i],A[largest]
        max_heapify(A,largest)

heap = [0]*2000000
for c in stdin:
    if c[0] == 'i':
        heap[0] += 1
        heap[heap[0]] = int(c[7:])
        i = heap[0]
        p = i/2
        while p > 0 and heap[p] < heap[i]:
            heap[p],heap[i] = heap[i],heap[p]
            i = p
            p = i/2
    elif c[1] == 'x':
        print heap[1]
        heap[1] = heap[heap[0]]
        heap[0] -= 1
        max_heapify(heap,1)
    else:
        break
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
    ans *= i
print(ans%(10**9+7))

### FIXED CODE ###

import math
n = int(input())
ans = math.factorial(n)
print(ans%(10**9+7))
### BUGGY CODE ###

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

ans=[]

for i in range(1,n):
    snuke=sum(a[0:i])
    raccoon=sum(a[i:])
    ans.append(abs(snuke-raccoon))

print(min(ans))


### FIXED CODE ###

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

ans=[]
snuke=0

for i in range(n-1):
    snuke+=a[i]
    ans.append(abs(X-2*snuke))

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

import sys


# sys.stdin = open('d1.in')


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


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    n = read_int()
    adj = [[] for u in range(n)]
    for i in range(n - 1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        adj[a].append((b, c))
        adj[b].append((a, c))

    d = [0] * n
    q, k = read_int_list()
    k -= 1

    Q = [(k, -1, 0)]
    while Q:
        u, parent, dist = Q.pop(0)
        Q.extend([(v, u, dist+w) for v, w in adj[u] if v != parent])
        d[u] = dist

    res = [0] * q
    for i in range(q):
        x, y = map(int, input().split())
        res[i] = d[x-1] + d[y-1]
    print(*res, sep='\n')


main()


### FIXED CODE ###

import sys
from collections import deque


# sys.stdin = open('d1.in')


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


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    n = read_int()
    adj = [[] for u in range(n+1)]
    for i in range(n - 1):
        a, b, c = map(int, input().split())
        adj[a].append((b, c))
        adj[b].append((a, c))

    d = [0] * (n+1)
    q, k = read_int_list()

    # Q = [(k, 0, 0)]
    Q = deque([(k, 0, 0)])
    while Q:
        u, parent, dist = Q.popleft()
        for v, w in adj[u]:
            if v != parent:
                Q.append((v, u, dist+w))
        d[u] = dist

    res = [0] * q
    for i in range(q):
        x, y = map(int, input().split())
        res[i] = d[x] + d[y]
    print(*res, sep='\n')


main()
### BUGGY CODE ###

N,M = map(int,input().split())
to = [[] for _ in range(N*3)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  to[a*3].append(b*3+1)
  to[a*3+1].append(b*3+2)
  to[a*3+2].append(b*3)
start,end = map(int,input().split())
start -= 1;end -= 1
#print(to)
INF = float("inf")
Stack = [start*3]
visit = [INF for _ in range(N*3)]
visit[start*3] = 0
while Stack:
  v = Stack.pop()
  for w in to[v]:
    if visit[w] <= visit[v]:
      continue
    visit[w] = min(visit[w],visit[v]+1) 
    Stack.append(w) #step歩目でwにいて次vへ行く。

#print(visit)
if visit[end*3] == INF:
  ans = -1
else:
  ans = visit[end*3]//3
print(ans)

### FIXED CODE ###

from collections import deque
N,M = map(int,input().split())
to = [[] for _ in range(N*3)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  to[a*3].append(b*3+1)
  to[a*3+1].append(b*3+2)
  to[a*3+2].append(b*3)
start,end = map(int,input().split())
start -= 1;end -= 1
#print(to)
INF = float("inf")
Q = deque([start*3])
visit = [INF for _ in range(N*3)]
visit[start*3] = 0
while Q:
  v = Q.popleft()
  for w in to[v]:
    if visit[w] != INF:
      continue
    visit[w] = visit[v]+1
    if w == end*3:
      print(visit[w]//3)
      exit()
    Q.append(w) #step歩目でwにいて次vへ行く。

#print(visit)
if visit[end*3] == INF:
  ans = -1
else:
  ans = visit[end*3]//3
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline
N, W = map(int, input().split())
w = np.zeros(N, dtype=int)
v = np.zeros(N, dtype=int)
for i in range(N):
  w[i], v[i] = map(int, input().split())
dp = np.zeros((N+1, W+1), dtype=int)
for i in range(1, N+1):
  for sum_w in range(1, W+1):
    if sum_w - w[i-1] >= 0:
      dp[i][sum_w] = max([dp[i-1][sum_w], dp[i-1][sum_w-w[i-1]] + v[i-1], dp[i][sum_w]])
    else:
      dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])
print(dp[N][W])

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline
N, W = map(int, input().split())
def knapsack():
  dp = np.zeros((N+1, W+1), dtype=int)
  c = np.arange(1, N+1)
  for i in c:
    w, v = map(int, input().split())
    dp[i][w:] = np.maximum(dp[i-1][w:], dp[i-1][:-w] + v)
    dp[i][:] = np.maximum(dp[i][:], dp[i-1][:])
  return dp[-1][-1]
print(knapsack())
### BUGGY CODE ###

import itertools
N, Ma, Mb = map(int, input().split())
r = Ma/Mb
costlist = []
data = [list(map(int, input().split())) for i in range(N)]
for i in range(1, max(N+1, 11)):
    combination = list(itertools.combinations(data, i))
    for k in range(len(combination)):
        a_tot = 0
        b_tot = 0
        c_tot = 0
        for j in range(len(combination[k])):
            a_tot += combination[k][j][0]
            b_tot += combination[k][j][1]
            c_tot += combination[k][j][2]
        if a_tot/b_tot == r:
            costlist.append(c_tot)
if costlist == []:
    print(-1)
else:
    print(min(costlist))


### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
r = Ma/Mb
a = 0
b = 0
costlist = [500000]
data = [list(map(int, input().split())) for i in range(N)]
for i in range(N):
    a += data[i][0]
    b += data[i][1]


dp = [[[500000 for i in range(N+1)] for i in range(b+10)] for i in range(a+10)]
dp[0][0][0] = 0

#Aがiグラム、Bがjグラム、k番目までの薬を用いたときの最小コスト
for k in range(N):
    for j in range(b):
        for i in range(a):
            ai = data[k][0]
            bj = data[k][1]
            dp[i+ai][j+bj][k+1] = min(dp[i+ai][j+bj][k+1], dp[i][j][k] + data[k][2])
            dp[i][j][k+1] = min(dp[i][j][k], dp[i][j][k+1])

for i in range(1, a):
    for j in range(1, b):
        if i/j == r:
            costlist.append(dp[i][j][N])
if N == 1:
    if data[0][0]/data[0][1] == r:
        print(data[0][2])
    else:
        print(-1)

elif min(costlist) == 500000:
    print(-1)
else:
    print(min(costlist))
### BUGGY CODE ###

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
a=[]
for i in range(3,10**5):
  if is_prime(i) and is_prime((i+1)//2):
    a.append(i)
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
for lri in lr:
  print(len([ai for ai in a if ai>=lri[0] and ai<=lri[1]]))

### FIXED CODE ###

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
a=[]
for i in range(3,10**5):
  if is_prime(i) and is_prime((i+1)//2):
    a.append(i)
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
for lri in lr:
  print(len([ai for ai in a if ai>=lri[0] and ai<=lri[1]]))
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
dp=[1]
if 1 in a:
  dp.append(0)
else:
  dp.append(1)
for i in range(2,n+1):
  if i in a:
    dp.append(0)
  else:
    dp.append(dp[-2]+dp[-1])
print(dp[n]%1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
a=0
cnt=1
p,q,r=1,0,0
#print(cnt,p)
for i in range(m):
  a=int(input())
  while cnt<n and cnt<a:
      s,r,q=r,q,p
      p=(q+r)%(10**9+7)
      cnt+=1
      #print(cnt,p)
  if a==cnt:
    s,r,q=r,q,p
    p=0
    cnt+=1
    #print(cnt,p)
    
while cnt<=n:
    s,r,q=r,q,p
    p=(q+r)%(10**9+7)
    cnt+=1
    #print(cnt,p)
print(p%(10**9+7))
### BUGGY CODE ###


import sys
input=sys.stdin.readline
n,y=map(int,input().split())
y10,y5,y1=0,0,0
for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            if 10000*i+5000*j+1000*k==y and i+j+k==n:
                print(i,j,k)
                exit(0)
print(-1,-1,-1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,y=map(int,input().split())
y10,y5,y1=0,0,0
for i in range(n+1):
    for j in range(n+1):
        k=n-i-j
        if 10000*i+5000*j+1000*k==y and k>=0:
            print(i,j,k)
            exit(0)
print(-1,-1,-1)
### BUGGY CODE ###

import math
n,a,b = map(int,input().split())
sump = 0
for r in range(1,n+1):
    if r ==a or r==b:
        continue
    sump += math.factorial(n) / (math.factorial(n - r) * math.factorial(r))
    if sump >= 10**9+7:
        sump = int(sump) %(10**9+7)
print(round(sump))

### FIXED CODE ###

#TRE
#pow(m,n)のnが大きい時は繰り返し2乗法を使う

#繰り返し2乗法のアルゴリズム
def modPow (a,n,p):
    if n==1:
        return a % p
    if n%2 == 1:
        return (a * modPow(a,n-1,p)) % p
    else:
        t = modPow(a,n/2,p)
        return t * t


#main
n,a,b = map(int,input().split())
p = 10**9+7
if n == 2 :
    print(0)
else:
#繰り返し2乗法により計算時間を短縮
    ans = modPow(2,n,p)-1#組み合わせのシグマは2のn乗
#組み合わせはn*...*(n-a+1)/(a*...*1)
    child_a = 1
    mother_a = 1
    for i in range(a):
        child_a = (child_a*(n-i))%p
        mother_a = (mother_a*(i+1))%p
    com_a = (child_a * modPow(mother_a,p-2,p)) % p
    child_b = 1
    mother_b = 1
    for i in range(b):
        child_b = (child_b*(n-i))%p
        mother_b = (mother_b*(i+1))%p
    com_b = (child_b * modPow(mother_b,p-2,p)) % p
    ans = (ans -(com_a+com_b))%p
    print(ans%p)
### BUGGY CODE ###

R, G, B, N = list(map(int, input().split()))

sum = 0
count = 0

len_R = N // R + 1
len_G = N // G + 1
len_B = N // B + 1

for ix in range(N // R + 2):
    for iy in range(N // G + 2):
        sum = N - (R * ix + G * iy)
        if sum >= 0 and sum % B == 0:
            count += 1
        if R * ix + G + iy > N:
            break
    if R * ix > N:
        break

print(count)

### FIXED CODE ###

R, G, B, N = list(map(int, input().split()))

count = 0

len_r = N // R + 2
for ix in range(len_r):
    len_g = (N - (R * ix)) // G + 2
    for iy in range(len_g):
        t = N - (R * ix + G * iy)
        if t >= 0 and t % B == 0:
            count += 1
print(count)
### BUGGY CODE ###

s = str(input())
num = 0
m = 1
for i in range(min(s.count('1'),s.count('0'))):
    t = num
    for i in range(len(s)-1):
        if (s[i]=='0' and s[i+1]=='1') or (s[i]=='1' and s[i+1]=='0'):
            num += 2
            s = s[:i]+ s[i+2:]
            break
    if t == num:
        break
print(num)

### FIXED CODE ###

s = str(input())
x = s.count('0')
y = s.count('1')
print(min(x,y)*2)
### BUGGY CODE ###

from collections import*
from itertools import*
from copy import*
n,m=map(int,input().split())

grid=[list("#"*(m+2))]+[list("#"+input()+"#")for i in range(n)]+[list("#"*(m+2))]

#print(grid)

start=[]
for i in range(1,n+1):
    for j in range(1,m+1):
        start.append((i,j))

ans=0
for s,g in combinations(start,2):
    G=deepcopy(grid)
    if G[s[0]][s[1]]!="#":
        G[s[0]][s[1]]=0
    else:
        continue
    if G[g[0]][g[1]]=="#":
        continue
    Q=deque([s])
    while Q:
        y,x=Q.pop()
        for my,mx in (-1,0),(1,0),(0,-1),(0,1):
            if G[y+my][x+mx]==".":
                G[y+my][x+mx]=G[y][x]+1
                Q.appendleft((y+my,x+mx))
    
    if type(G[g[0]][g[1]])!=str:
        if ans<G[g[0]][g[1]]:
            ans=G[g[0]][g[1]]
print(ans)

### FIXED CODE ###

from collections import*
from copy import*
n,m=map(int,input().split())

grid=[list("#"*(m+2))]+[list("#"+input()+"#")for i in range(n)]+[list("#"*(m+2))]
#print(grid)

start=[]
for i in range(1,n+1):
    for j in range(1,m+1):
        start.append((i,j))

ans=0
for s in start:
    G=deepcopy(grid)
    if G[s[0]][s[1]]!="#":
        G[s[0]][s[1]]=0
    else:
        continue
    Q=deque([s])
    while Q:
        y,x=Q.pop()
        for my,mx in (-1,0),(1,0),(0,-1),(0,1):
            if G[y+my][x+mx]==".":
                G[y+my][x+mx]=G[y][x]+1
                Q.appendleft((y+my,x+mx))
    
    x=max( max([0]+[j for j in i  if type(j)==int]) for i in G)
    if x>ans:
        ans=x
print(ans)
### BUGGY CODE ###

import sys
from itertools import combinations
import bisect
import math
import numpy as np
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
l_dict = { i : j for i, j in enumerate(l_ls)}
_sum_ls = []
cnt = 0
count_ls = np.zeros(2*10**3, dtype=np.int)
for combi in combinations(l_ls, 2):
    count_ls[combi[0] + combi[1]:] += 1
    #bisect.insort_left(_sum_ls, combi[0] + combi[1])
len_sum_ls = len(_sum_ls)
for l in l_ls:
    #ind = bisect.bisect_right(_sum_ls, l)
    ind = count_ls[l]
    cnt += ind
print(int(math.factorial(n) / math.factorial(3) / math.factorial(n-3)) - cnt)

### FIXED CODE ###

import sys
from itertools import combinations
import bisect
import math
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
cnt = 0
for a, b in combinations(l_ls, 2):
    _sum = a + b
    ind = bisect.bisect_left(l_ls, _sum)
    cnt += n - ind
print(int(math.factorial(n) // math.factorial(3) // math.factorial(n-3)) - cnt)
### BUGGY CODE ###

# coding:UTF-8
import sys


def resultSur97(x):
    return x % (10 ** 9 + 7)


if __name__ == '__main__':
    # ------ 入力 ------#
    # 1行入力
    n = int(input())    # 数字
    aList = list(map(int, input().split()))     # スペース区切り連続数字

    # ------ 処理 ------#
    sum = 0
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            sum += aList[i-1]*aList[j-1]

    out = resultSur97(sum)

    # ------ 出力 ------#
    print("{}".format(out))
    # if flg == 0:
    #     print("YES")
    # else:
    #     print("NO")


### FIXED CODE ###

# coding:UTF-8
import sys


def resultSur97(x):
    return x % (10 ** 9 + 7)


if __name__ == '__main__':
    # ------ 入力 ------#
    # 1行入力
    n = int(input())    # 数字
    aList = list(map(int, input().split()))     # スペース区切り連続数字

    # ------ 処理 ------#
    sum = 0
    for i in range(0, n):
        sum += aList[i]

    pro = 0
    for i in range(0, n):
        ai = aList[i]
        sum = sum - ai
        pro += sum * aList[i]

    out = resultSur97(pro)

    # ------ 出力 ------#
    print("{}".format(out))
    # if flg == 0:
    #     print("YES")
    # else:
    #     print("NO")
### BUGGY CODE ###

a,b=map(int,input().split())
import sys
ans=1

for i in range(a,b+1):
    if i == 0:
        print('Zero')
        sys.exit()
    ans*=i
    
if 0 < ans:
    print('Positive')
elif ans == 0:
    print('Zero')
else:
    print('Negative')

### FIXED CODE ###

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

if 0<a<b:
    print('Positive')

elif a<=0<=b:
    print('Zero')

elif (b-a)%2==0:
    print('Negative')
else:
    print('Positive')
### BUGGY CODE ###

from collections import deque

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

inp = []
for h in range(H):
    inp.append(input())

field = []
field.append(["#" for _ in range(W+2)])
for h in range(H):
    field.append(["#"] + list(inp[h]) + ["#"])    
field.append(["#" for _ in range(W+2)])


def bfs():
    que = deque([])
    next_h = [1,0,-1, 0]
    next_w = [0,1, 0,-1]
    
    que.append([0,1,1])
    
    while len(que) != 0:
        dist,h,w = que.popleft()
        field[h][w] = str(dist)
        
        for i in range(4):
            if field[h+next_h[i]][w+next_w[i]] == ".":
                que.append([dist+1, h+next_h[i], w+next_w[i]])
            
    return field[H][W]
    

points = 0
for field_row in field:
    for point in field_row:
        if point == ".":
            points += 1


min_dist = bfs()

if min_dist == '.':
    print(-1)
else:
    print(points - int(min_dist) - 1)

### FIXED CODE ###

from collections import deque

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

inp = []
for h in range(H):
    inp.append(input())

field = []
field.append(["#" for _ in range(W+2)])
for h in range(H):
    field.append(["#"] + list(inp[h]) + ["#"])    
field.append(["#" for _ in range(W+2)])


def bfs():
    que = deque([])
    next_h = [1,0,-1, 0]
    next_w = [0,1, 0,-1]
    
    que.append([0,1,1])
    
    while len(que) != 0:
        dist,h,w = que.popleft()
        if field[h][w] != ".":
            continue
        
        field[h][w] = str(dist)
        
        for i in range(4):
            if field[h+next_h[i]][w+next_w[i]] == ".":
                que.append([dist+1, h+next_h[i], w+next_w[i]])
            
    return field[H][W]
    

points = 0
for field_row in field:
    for point in field_row:
        if point == ".":
            points += 1


min_dist = bfs()

if min_dist == '.':
    print(-1)
else:
    print(points - int(min_dist) - 1)
### BUGGY CODE ###

while 1:
  h,w=map(int,raw_input().split())
  if h==w==0: break
  W=range(w)
  a=[0]*w
  s=0
  for _ in [0]*h:
    b=raw_input()
    f=[0]*w
    for i in W:
      f[i]=[a[i]+1,0][b[i]=="*"]
      m=1e9
      for j in range(i+1):
        m=min(f[j:i+1])
        if m!=0: s=max(s,m*(i+1-j))
    a=f
  print s

### FIXED CODE ###

while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  M = [0]*(h+1)
  a=[0]*w
  for i in range(h):
    x = raw_input()
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]=="*": c=0
      else: c=a[j]+1
      b[j]=c
      dw=c-sp
      if dw>0: C[sp+1:c+1]=[j]*dw
      elif dw<0:
        for k in range(c+1,sp+1): M[k]=max(M[k],j-C[k])
        C[c+1:sp+1]=[-1]*(-dw)
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0: M[k]=max(M[k],w-C[k])
    a=b
  s=max([a*b for a,b in zip(M, range(h+1))])
  print s
### BUGGY CODE ###

inputs = input().split(' ')
a = int(inputs[0])
b = int(inputs[1])
n = int(inputs[2])

output = 0
for x in range(1, n + 1):
    if x % (a * b) == 0:
        break
    buf = (a*x//b) - a*(x//b)
    if buf > output:
        output = buf

print(output)

### FIXED CODE ###

inputs = input().split(' ')
a = int(inputs[0])
b = int(inputs[1])
n = int(inputs[2]) + 1

x = (n if n < b else b) - 1
output = (a*x//b)

print(output)