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

import math,itertools,fractions,heapq,bisect,sys,copy,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0

  for i in range(h):
    for j in range(w):
      for k in range(h):
        for l in range(w):
          q=collections.deque()
          if field[i][j]=='#' or field[k][l]=='#':
            continue
          q.append((k,l,0))
          visited=[[-1]*w for _ in range(h)]
          while len(q)>0:
            y,x,c=q.popleft()
            if visited[y][x]!=-1:
              continue
            visited[y][x]=c
            if y==i and x==j:
              ans=max(ans,c)
              break

            for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
              ny=y+dy
              nx=x+dx
              if 0<=ny<h and 0<=nx<w:
                if field[ny][nx]=='#':
                  continue
                if visited[ny][nx]!=-1:
                  continue
                q.append((ny,nx,c+1))

  return ans

# main()
print(main())


### FIXED CODE ###

import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      visited[i][j]=0
      _ans=0
      while q:
        y,x=q.popleft()

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if not 0<=ny<h:
            continue
          if not 0<=nx<w:
            continue
          if field[ny][nx]=='#':
            continue
          if visited[ny][nx]!=-1:
            continue
          _ans=visited[y][x]+1
          visited[ny][nx]=_ans
          q.append((ny,nx))
      ans=max(ans,_ans)
  return ans

# main()
print(main())
### BUGGY CODE ###

def num_of_inversions(A, n):
    """Print the number of inversions in the sequence A.

    A is a list of numbers.
    n is the length of A.
    """

    cnt = 0
    for i in range(n - 1):
        flag = 0
        for j in range(n - 1, i, -1):
            if A[j] < A[j - 1]:
                A[j], A[j - 1] = A[j - 1], A[j]
                cnt += 1
                flag = 1
        if flag == 0:
            break
    print(cnt)


import sys

n = int(sys.stdin.readline())

A = list(map(int, sys.stdin.readline().split()))

num_of_inversions(A, n)

### FIXED CODE ###

sentinel = 1000000001

def merge(A, left, mid, right):
    L = A[left:mid]
    n1 = len(L)
    L.append(sentinel)
    R = A[mid:right]
    R.append(sentinel)
    i = 0
    j = 0
    cnt = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            cnt += n1 - i
    return cnt

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        cnt1 = mergeSort(A, left, mid)
        cnt2 = mergeSort(A, mid, right)
        cnt3 = merge(A, left, mid, right)
        return cnt1 + cnt2 + cnt3
    else:
        return 0


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

cnt = 0

n_ivs =  mergeSort(S, 0, n)

print(n_ivs)
### BUGGY CODE ###

x,y,a,b,c = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

p2 = p[:x]
q2 = q[:y]

for i in range(c):
  if p2[-1] <= q2[-1] and p2[-1] < r[i]:
    p2[-1] = r[i]
    p2.sort(reverse=True)
  if p2[-1] > q2[-1] and q2[-1] < r[i]:
    q2[-1] = r[i]
    q2.sort(reverse=True)
    
ans = sum(p2)+sum(q2)
print(ans)

### FIXED CODE ###

x,y,a,b,c = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))

p.sort(reverse=True)
q.sort(reverse=True)

p2 = p[:x]
q2 = q[:y]

l = p2 + q2 + r
l.sort(reverse=True)

ans = sum(l[:x+y])
print(ans)
### BUGGY CODE ###

N, Q = map(int,input().split())
S= input()
lr_list = [list(map(int,input().split())) for _ in range(Q)]
ac_tf_list = [1 if S[i:i+2]=='AC' else 0 for i in range(N-1)]

for i in range(Q):
    ans = sum(ac_tf_list[lr_list[i][0]-1:lr_list[i][1]-1])
    print(ans)

### FIXED CODE ###

N, Q = map(int,input().split())
S= input()
lr_list = [list(map(int,input().split())) for _ in range(Q)]

# ac_tf_list = [1 if S[i:i+2]=='AC' else 0 for i in range(N-1)]
t = [0]*N
for i in range(N-1):
    if S[i:i+2]=='AC':
        t[i+1] = t[i]+1
    else:
        t[i+1] = t[i]

for i in range(Q):
    l = lr_list[i][0]-1
    r = lr_list[i][1]-1
    print(t[r]-t[l])
### BUGGY CODE ###

from bisect import bisect_left
N = int(input())
L = list(map(int,input().split()))
L_1 = sorted(L)

ans = 0

for i in range(N-1):
  for j in range(i+1,N-1):
      A = bisect_left(L_1,L_1[i]+L_1[j])
      for k in range(j+1,A):
          if L_1[i]+L_1[j] > L_1[k]:
              ans += 1
      
print(ans)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = list(map(int,input().split()))
L_1 = sorted(L)

ans = 0

for i in range(N-1):
  for j in range(i+1,N-1):
      ans +=bisect_left(L_1,L_1[i]+L_1[j])-j-1
print(ans)
### BUGGY CODE ###

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

s = input().rstrip()
q = int(input())
query = [input().split() for _ in range(q)]

flag = False
for i in range(q):
    qq = query[i]
    if qq[0] == '1':
        flag = not(flag)
    else:
        if flag:
            if qq[1] == '1':
                s = s + qq[2]
            else:
                s = qq[2] + s
        else:
            if qq[1] == '1':
                s = qq[2] + s
            else:
                s = s + qq[2]

if flag:
    print(s[::-1])
else:
    print(s)


### FIXED CODE ###

import sys
from collections import deque

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

s = input().rstrip()
q = int(input())
d = deque()
d.append(s)

flag = False
for i in range(q):
    qq = input().split()
    if qq[0] == '1':
        flag = not(flag)
    else:
        if flag:
            if qq[1] == '1':
                d.append(qq[2])
            else:
                d.appendleft(qq[2])
        else:
            if qq[1] == '1':
                d.appendleft(qq[2])
            else:
                d.append(qq[2])

ans = ''.join(list(d))
if flag:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
r = max(a)+1
s = []
t = [0]*r
for i in range(r):
    s.append([])
for i in range(2,r):
    for j in range(1,-(-r//i)):
        s[i*j].append(i)
for i in range(n):
    for j in range(len(s[a[i]])):
        t[s[a[i]][j]] += 1
if(max(t) == n):
    print('not coprime')
elif(max(t) <= 1):
    print('pairwise coprime')
else:
    print('setwise coprime')

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
r = max(a)+1
s = []
t = [0]*r
for i in range(r):
    s.append([])
for i in range(2,r):
    if(s[i] == []):
        for j in range(1,-(-r//i)):
            s[i*j].append(i)
for i in range(n):
    for j in range(len(s[a[i]])):
        t[s[a[i]][j]] += 1
if(max(t) == n):
    print('not coprime')
elif(max(t) <= 1):
    print('pairwise coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

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

A_count = dict()
for i in set(A):
	A_count.update({i:len([j for j in A if j == i])})

A_sort = sorted(A_count.values())[::-1]
print(sum(A_sort[K:]))

### FIXED CODE ###

from collections import Counter

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

A_count = Counter(A)

A_sort = sorted(A_count.values())[::-1]
print(sum(A_sort[K:]))
### BUGGY CODE ###

n = int(input())
cnt=[]
for _ in range(n):
    a=int(input())
    if a in cnt:
        cnt.remove(a)
    else:
        cnt.append(a)
print(len(cnt))

### FIXED CODE ###

import collections
n=int(input())
a=[int(input()) for _ in range(n)]
c = collections.Counter(a)
ans=0
for k,v in c.items():
    if v % 2 != 0:
        ans += 1
print(ans)
### BUGGY CODE ###

from collections import deque
n =int(input())
takahashi = 0
aoki = 0
a = [[int(i) for i in input().split()] for i in range(n)] 
a2 = sorted(a, key=lambda x: x[0])
d = deque(a2)
start = 0
for i in range(n):
 if start%2 == 0:
  d = sorted(d, key=lambda x: x[0])
  a,b =d.pop()
  takahashi += a
  #print(d)
 if start %2 == 1:
  d = sorted(d, key=lambda x: x[1])
  a,b = d.pop()
  aoki += b
  #print(d)
 start += 1
print(takahashi -aoki)

### FIXED CODE ###

from collections import deque
n =int(input())
takahashi = 0
aoki = 0
ab = []
a = []
for i in range(n):
 tmp1,tmp2 = (int(i) for i in input().split())
 a.append([tmp1,tmp2])
 ab.append(tmp1+tmp2)
 aoki += tmp2
#a2 = sorted(a, key=lambda x: x[0])
#a3 = sorted(a, key=lambda x: x[1])
ab = sorted(ab,reverse = True)
start = 0
for i in range(n):
  if i%2 == 0:
    takahashi += ab[i]
  else:
    continue


print(takahashi-aoki)
### BUGGY CODE ###

import collections
n, m = map(int, input().split())
linked = collections.defaultdict(set)
for i in range(1, n + 1):
  linked[i] = [i]
 
for i in range(m):
  a, b = map(int, input().split())
  if linked[a] == linked[b]: continue
  linked[a].extend(linked[b])
  for t in linked[b]:
    linked[t] = linked[a]
 
n_connected = 0
n_group = 0
for s in linked.values():
  if s:
    n_group += 1
    n_connected += len(s)
    s.clear()
print((n - n_connected) + (n_group - 1))

### FIXED CODE ###

import collections
n, m = map(int, input().split())
linked = collections.defaultdict(list)
i2group = dict()

gid = n + 1
def get_root(i):
  if i not in linked:
    return i
  j = get_root(linked[i])
  linked[i] = j
  return j

def get_groups():
  return [get_root(i) for i in range(1, n + 1)]

for i in range(m):
  a, b = map(int, input().split())
  ra, rb = get_root(a), get_root(b)
  if ra == rb: continue
  linked[ra] = gid
  linked[rb] = gid
  gid += 1

g = get_groups()
print(len(set(g)) - 1)
exit()

n_connected = 0
n_group = 0
for s in linked.values():
  s = s[0]
  if s:
    n_group += 1
    n_connected += len(s)
    s.clear()
print((n - n_connected) + (n_group - 1))
### BUGGY CODE ###

n = int(input())

w = {}
for _ in range(n):
    s = input()
    w[s] = w.get(s, 0) + 1
ans = sorted(i for i, j in w.items() if j == max(w.values()))
for i in ans:
    print(i)


### FIXED CODE ###

n = int(input())
s = list(input() for _ in range(n))
s.sort()
now = s[0]
ans = [s[0],]
cnt = 0
m_cnt = 0

for i in range(n):
    word = s[i]
    if word == now:
        cnt +=1
        if cnt > m_cnt:
            ans = [word,]
            m_cnt = cnt
        elif cnt == m_cnt:
            ans.append(word)
    else:
        cnt = 1
        now = word
        if cnt > m_cnt:
            ans = [word,]
            m_cnt = cnt
        elif cnt == m_cnt:
            ans.append(word)

for k in sorted(ans):
    print(k)
### BUGGY CODE ###

import sys
n=int(input())

def bin(start):
    ok=0
    ng=n
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid)
        sys.stdout.flush()
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        if mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
print(0)
start=input()
sys.stdout.flush()
if start=='Vacant':exit()
bin(start)


### FIXED CODE ###

import sys
n=int(input())

def bin(start):
    ok=0
    ng=n
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid)
        sys.stdout.flush()
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        elif mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
print(0)
start=input()
sys.stdout.flush()
if start=='Vacant':exit()
bin(start)
### BUGGY CODE ###

from heapq import *

n,m,s,t=map(int,input().split())
s-=1
t-=1
INF=10**19
Gyen=[[]for i in range(n)]
Gsnu=[[]for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  Gyen[u].append([v,a])
  Gyen[v].append([u,a])
  Gsnu[u].append([v,b])
  Gsnu[v].append([u,b])

def dijkstra(G,s):
  que=[]
  d=[INF]*n
  d[s]=0
  visited={s}
  heappush(que,[0,s])
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    if d[v]<p[0]:
      continue
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,[d[node],node])
  return d

yen=dijkstra(Gyen,s)
snu=dijkstra(Gsnu,t)
ans=10**15
ans_list=[]
for i in reversed(range(n)):
  ans=min(ans,yen[i]+snu[i])
  ans_list.append(10**15-ans)
print(*ans_list[::-1], sep='\n')


### FIXED CODE ###

from heapq import *

n,m,s,t=map(int,input().split())
s-=1
t-=1
INF=10**19
Gyen=[[]for i in range(n)]
Gsnu=[[]for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  Gyen[u].append([v,a])
  Gyen[v].append([u,a])
  Gsnu[u].append([v,b])
  Gsnu[v].append([u,b])

def dijkstra(G,s):
  que=[]
  d=[INF]*n
  d[s]=0
  visited={s}
  heappush(que,[0,s])
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,[d[node],node])
  return d

yen=dijkstra(Gyen,s)
snu=dijkstra(Gsnu,t)
ans=10**15
ans_list=[]
for i in reversed(range(n)):
  ans=min(ans,yen[i]+snu[i])
  ans_list.append(10**15-ans)
print(*ans_list[::-1], sep='\n')
### BUGGY CODE ###

n = int(input())
lists = []
for i in range(n):
    a = input()
    k = []
    for i in range(10):
        k.append(a[i])
    k.sort()
    lists.append(k)
count = 0
for i in range(n-1):
    for j in range(i+1,n):
        if lists[i] == lists[j]:
            count+=1
print(count)


### FIXED CODE ###

n = int(input())
lists = []
for i in range(n):
    a = input()
    k = []
    for i in range(10):
        k.append(a[i])
    k.sort()
    lists.append(k)
lists.sort()
lists.append([])
count = -1
ans = 0
for i in range(n):
    if lists[i] != lists[i+1]:
        c = i-count
        count = i
        ans += c*(c-1)//2
print(ans)
### BUGGY CODE ###

import bisect
N = int(input())
l = [int(x) for x in input().split()]
l.sort()
ans = 0
for i in range(1,N-1):
  for j in range(i+1, N):
    a = l[:-j]
    L = len(a)
    if l[-j] - (l[-i]-1) < (l[-i] + 1) - l[-j]: m = (l[-i]+1) - l[-j]
    else : m = l[-j]-(l[-i]-1)
    n = bisect.bisect_left(a, m)
    ans += (L - n)
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
from bisect import bisect_left
for i in range(n-2):
  for j in range(i+1, n-1):
    ab = l[i] + l[j]
    idx = bisect_left(l, ab)
    ans += max(idx-j-1, 0)
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
gateInfos = [list(map(int,input().split()))for i in range(M)]
c = 0

cards = [True]*N

for g in gateInfos:
  L = g[0]
  R = g[1]
  for i in range(L-1):
    cards[i] = False
  for i in range(R,N):
    cards[i] = False
print(cards.count(True))

### FIXED CODE ###

N,M = map(int,input().split())
maL = 0
miR = N
for g in range(M):
  L,R = map(int,input().split())
  maL = max(maL,L)
  miR = min(miR,R)
if maL <= miR:
  print(miR-maL+1)
else:
  print(0)
### BUGGY CODE ###

import sys
N = int(input())
A = list(map(int, input().split()))

if not 1 in A:
    print(-1)
    sys.exit()

i_min = A.index(1)
m = 1
cnt = 1

for i in range(i_min, len(A)):
    
    if m + 1 in A[i_min + 1:]:
        i_min = A.index(m + 1)
        m += 1
        cnt += 1
        
    if i_min == 0:
        break

print(len(A) - cnt)

### FIXED CODE ###

import sys
N = int(input())
A = list(map(int, input().split()))

find = 1

for i in range(N):
    if A[i] == find:
        find += 1

print(-1 if find == 1 else len(A) - find + 1)
### BUGGY CODE ###

import copy

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

n = 0
C = set(A)

for k in C:
    cnt = A.count(k)
    n +=  cnt * (cnt-1) // 2

for k in range(N):
    a = A[k]
    print(n - A.count(a) + 1)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))

n = 0
B = set(A)

C = Counter(A)

for i in C.keys():
    n += C[i] * (C[i]-1) // 2

for i in range(N):
    a = A[i]
    print(n - C[a] + 1)
### BUGGY CODE ###

s=int(input())
flag=False
if s<=10**9:
  li=[0,0,1,0,0,s]
else:
  a=b=int(s**(1/2))
  while True:
    c = s-a*b
    if c == 0:
      d=0;break
    sc = int(c**(1/2))
    for i in range(sc,sc+100):
      if c%i==0 and a+c<=10**9:
        d=i;c=c//i
        flag = True
        break
    if flag:
      break
    a -= 1
  li = [c,0,a+c,d,0,b]
for num in li:
  print(num,end=" ")

### FIXED CODE ###

s = int(input())
if s==10**18:
  print(0,0,10**9,0,0,10**9)
else:
  print(0,0,s//10**9+1,1,10**9-s%10**9,10**9)
### BUGGY CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a

N = int(input())
A = list(map(int, input().split()))
if N == 1:
    print('1')
else:
    gcd = xgcd(A[0],A[1])
    lcm = (A[0] * A[1]) // gcd
    for i in range(2,N):
        gcd = xgcd(lcm,A[i])
        lcm = (lcm * A[i]) // gcd
    print(sum([lcm // x for x in A])%1000000007)

### FIXED CODE ###

from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
if N == 1:
    print('1')
else:
    g = gcd(A[0],A[1])
    lcm = (A[0]*A[1]) // g
    for x in A[2:]:
        lcm = (lcm * x) // gcd(lcm,x)
    print(sum((lcm//x) for x in A)%1000000007)
### BUGGY CODE ###

import sys
import random
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

import math
A, B, N = MII_split()

def f(x):
    """最小値を求めたい関数"""
    return math.floor(A * x / B) - A * math.floor(x / B)

def numerical_diff(f, x, h=B):
    """中央差分を元に数値微分する関数"""
    return (f(x + h) - f(x - h)) / (2 * h)

# def f_diff(f, x, h=B):
#     return f(x + h) - f(x)

def gradient_descent(f, initial, learning_rate=1, steps=10 ** 4):
    """一階導関数から勾配法で最小値を求める関数"""
    # 現在地を示すカーソル
    x = initial

    # 所定の回数を繰り返す
    for step in range(steps):
        # 現在地の勾配 (どちらにどれだけ進むべきか) を得る
        grad = 0
        count = 1
        while grad == 0:
            h = B * count
            grad = numerical_diff(f, x, h=h)
            count += 1
        x -= learning_rate * grad
        if x < 0:
            x = 0
        elif x > N:
            x = N

    # 最終的な位置を返す
    return f(x)

ma = 0
for x in range(B):
    if x > N: break
    # ini = random.randrange(N + 1)
    # tmp = gradient_descent(f, ini)
    tmp = f(x)
    if ma < tmp:
        ma = tmp

print(ma)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

import math

A, B, N = MII_split()

def f(x):
    return math.floor(A * x / B) - A * math.floor(x / B)

# max = 0
# for x in range(min(B + 1, N + 1)):
#     if x > N:
#         break
#     fx = f(x)
#     # print(fx)
#     if fx > max:
#         max = fx
print(f(min(B-1, N)))
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)

n = int(input())
graph = {i : [] for i in range(n)}
ls = []
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    ls.append((a,b))
    graph[a].append(b)
    graph[b].append(a)
_max = 0
_max_node = None
for k, v in graph.items():
    if len(v) > _max:
        _max = len(v)
        _max_node = k
colors = [[0 for i in range(n)] for j in range(n)]
que = deque()
color_dict = {i : set(range(1,1+_max)) for i in range(n)}
cur = _max_node
already = set()
while True:
    cnt = 1
    already.add(cur)
    for _next in graph[cur]:
        if colors[cur][_next] == 0:
            if _next not in already:
                que.append(_next)
                already.add(_next)
            candidate = color_dict[_next].intersection(color_dict[cur])
            cnt = list(candidate)[0]
            colors[cur][_next] = cnt
            colors[_next][cur] = cnt
            color_dict[cur].remove(cnt)
            color_dict[_next].remove(cnt)
    if len(que) == 0:
        break
    cur = que.popleft()
print(_max)
for a, b in ls:
    print(colors[a][b])

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)

n = int(input())
graph = {i : [] for i in range(n)}
ls = []
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    ls.append((a,b))
    graph[a].append(b)
    graph[b].append(a)
_max = 0
_max_node = None
for k, v in graph.items():
    if len(v) > _max:
        _max = len(v)
        _max_node = k

parent = [_max_node] * (n)
order = []
stack = [_max_node]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

colors = [-1 for i in range(n)]
for i in order:
    c = 1
    for _next in graph[i]:
        if _next == parent[i]:
            continue
        if c == colors[i]:
            c += 1
        colors[_next] = c
        c += 1
print(_max)
for a, b in ls:
    if parent[a] == b:
        print(colors[a])
    else:
        print(colors[b])
### BUGGY CODE ###

N,M=map(int,input().split());D=[9e9for _ in range(2**N)];D[0]=0
for i in range(M):
 a,_=input().split();s=sum(2**~-int(c)for c in input().split())
 for j in range(2**N):D[s|j]=min(D[s|j],D[j]+int(a))
print(-1*(D[-1]>8e9)or D[-1])

### FIXED CODE ###

N,M=map(int,input().split());D=[0]+[9**9]*(1<<N)
for i in range(M):
 a=int(input().split()[0]);s=sum(1<<~-int(c)for c in input().split())
 for j in range(1<<N):D[s|j]=min(D[s|j],D[j]+a)
print(D[-2]%(9**9)or-1)
### BUGGY CODE ###

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

ans = 0
answer = 0

for i in range(n-k+1):
    total = sum(pp[i:i+k])
    if ans <= total:
        ans = max(ans, total)
        num = i

for n in range(k):
    answer += (1+pp[num+n])/2

print(answer)


### FIXED CODE ###

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

answer = sum(pp[:k])
total = sum(pp[:k])

for i in range(n-k):
    total = total - pp[i] + pp[i+k]
    answer = max(answer, total)

print((answer+k)/2)