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

n=int(input())
s_list=[''.join(sorted(input())) for i in range(n)]
c = 0
s_list_exist = []
for s in s_list:
  if not s in s_list_exist and s_list.count(s) != 1:
    c += s_list.count(s) * (s_list.count(s)-1) // 2
    s_list_exist.append(s)
print(c)

### FIXED CODE ###

n=int(input())
s_list=[''.join(sorted(input())) for i in range(n)]
c = 0
words = {}
for s in s_list:
  time = words.get(s,0)
  c += time
  words[s] = time + 1
print(c)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[0 for i in range(m)]
b=[0 for i in range(m)]
c=[[] for i in range(m)]
for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=list(map(int,input().split()))
dp = [float("inf") for i in range(2**n)]
dp[0] = 0
for i in range(m):
    now = 0
    for j in c[i]:
        jj = 1<< j-1
        now |= jj
    for k in range(2**n):
        kk = k | now
        dp[kk] = min(dp[kk], dp[k]+a[i])
if dp[-1]==float("inf"):
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

def main():
  n,m=map(int,input().split())
  a=[0 for i in range(m)]
  b=[0 for i in range(m)]
  c=[[] for i in range(m)]
  for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=list(map(int,input().split()))
  
  dp=[float("inf") for i in range(2**n)]
  dp[0]=0
  for i in range(m):
    now=0
    for j in c[i]:
      jj=1<<j-1
      now|=jj
    for k in range(2**n):
      kk=k|now
      dp[kk]=min(dp[kk],dp[k]+a[i])
    
 
  if dp[-1]==float("inf"):
    print(-1)
  else:
    print(dp[-1])
    
if __name__ == '__main__':  
  main()
### BUGGY CODE ###

s = input()
t = input()

c=0
j=-1
k=1

a=len(s)

for i in range(0,len(t)):
  while True:
    j=j+1
    c=c+1

    if j>=a:
      j=0

    if t[i:i+1]==s[j:j+1]:
      k=1
      break
    else:
      k=k+1
      if k>a+1:
        print("-1")
        exit()
print(c)


### FIXED CODE ###

s = input()
t = input()

x = len(s)
y = len(t)

a = 0
b = x
c = 0
a0 = 0


for i in range(0,y):
  while True:
    #先頭からの位置
    a=s.find(t[i:i+1],a0)+1
    if a <= 0:
      a=s.find(t[i:i+1])+1
    if a <= 0:
      print("-1")
      exit()
    
    if a<=a0:
      c=c+a+b
    else:
      c=c+a-a0
    b=x-a
    a0=a
    break
    
print(c)
### BUGGY CODE ###

h, w = map(int, input().split())
meiro = []
for i in range(h):
    line = input()
    meiro.append(line)


def dfs(y, x):
    dist = [[-1]*w for _ in range(h)]
    if meiro[y][x] == '#':
        return 0
    dist[y][x] = 0

    pattern = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    todo = []
    for dy, dx in pattern:
        ny, nx = y + dy, x + dx
        if 0 <= ny <= h-1 and 0 <= nx <= w-1:
            todo.append([ny, nx, 1])

    while todo:
        y, x, d = todo.pop()
        if meiro[y][x] == '#':
            continue
        if dist[y][x] != -1:
            if dist[y][x] <= d:
                continue

        dist[y][x] = d
        for dy, dx in pattern:
            ny, nx = y + dy, x + dx
            if 0 <= ny <= h - 1 and 0 <= nx <= w - 1:
                todo.append([ny, nx, d+1])

    res = 0
    for line in dist:
        res = max(max(line), res)

    return res


ans = []
for y in range(h):
    for x in range(w):
        ans.append(dfs(y, x))

print(max(ans))


### FIXED CODE ###

import heapq


h, w = map(int, input().split())
meiro = []
for i in range(h):
    line = input()
    meiro.append(line)


def dfs(y, x):
    dist = [[-1]*w for _ in range(h)]
    if meiro[y][x] == '#':
        return 0
    dist[y][x] = 0

    pattern = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    todo = []
    for dy, dx in pattern:
        ny, nx = y + dy, x + dx
        if 0 <= ny <= h-1 and 0 <= nx <= w-1:
            if meiro[ny][nx] == '.':
                heapq.heappush(todo, [1, ny, nx])

    while todo:
        d, y, x = heapq.heappop(todo)
        if meiro[y][x] == '#':
            continue
        if dist[y][x] != -1:
                continue

        dist[y][x] = d
        for dy, dx in pattern:
            ny, nx = y + dy, x + dx
            if 0 <= ny <= h - 1 and 0 <= nx <= w - 1:
                if dist[ny][nx] == -1 and meiro[ny][nx] == '.':
                    heapq.heappush(todo, [d+1, ny, nx])

    res = 0
    for line in dist:
        res = max(max(line), res)

    return res


ans = []
for y in range(h):
    for x in range(w):
        ans.append(dfs(y, x))

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

N, M = map(int, input().split())
A, C = [], []
for _ in range(M):
    a, _ = map(int, input().split())
    A.append(a)
    C.append(sum(2 ** (i - 1) for i in map(int, input().split())))

table = [float('inf')] * 2 ** N
table[0] = 0
for m in range(M):
    for x in range(2 ** N):
        an = x | C[m]
        table[an] = min(table[an], table[x] + A[m])
ans = table[2 ** N - 1]

print(ans if ans != float('inf') else -1)


### FIXED CODE ###

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

p2 = 2 ** N
table = [10 ** 9] * p2
table[0] = 0
for m in range(M):
    a, _ = map(int, input().split())
    c = sum(2 ** (i - 1) for i in map(int, input().split()))
    for x in range(p2):
        an = x | c
        table[an] = min(table[an], table[x] + a)
ans = table[p2 - 1]
 
print(ans if ans != 10 ** 9 else -1)
### BUGGY CODE ###

n=int(input())
s=input()
l=0
r=n//2
while r-l>=1:
    m=(r+l+1)//2
    list=[]
    flg=False
    for i in range(n-m+1):
        t=s[i:i+m]
        if t in list:
            if t in s[:i]:
                flg=True
                break
        else:
            list.append(t)
    if flg:
        l=m
    else:
        r=m-1
print(l)

### FIXED CODE ###

n=int(input())
s=input()
l=0
r=n//2
while r-l>=1:
    m=(r+l+1)//2
    d={}
    flg=False
    for i in range(n-m+1):
        t=s[i:i+m]
        if t in d:
            if d[t]+m-1<i:
                flg=True
                break
        else:
            d[t]=i
    if flg:
        l=m
    else:
        r=m-1
print(l)
### BUGGY CODE ###

N,M = map(int,input().split())
a = []
for i in range(N):
    array = list(map(int,input().split()))
    a.append(array)
a.sort()
ans = 0
bought = 0
while bought!=M:
    b=a.pop(0)
    if bought+b[1]>M:
        ans+= b[0]*(M-bought)
        bought=M
        print(ans)
        exit()
    ans += b[0]*b[1]
    bought += b[1]
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
a = []
for i in range(N):
    array = list(map(int,input().split()))
    a.append(array)
a.sort()
ans = 0
bought = 0
for i in range(N):
    if bought+a[i][1]>M:
        ans+= a[i][0]*(M-bought)
        bought=M
        print(ans)
        exit()
    ans += a[i][0]*a[i][1]
    bought += a[i][1]
print(ans)
### BUGGY CODE ###

import itertools

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]

for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

taisen = list(itertools.combinations(range(n), 2))
taisen_dic = {}
for i in range(len(taisen)):
    taisen_dic[taisen[i]] = i

B = [[0] * (n-1) for i in range(n)]

for i in range(n):
    for j in range(n-1):
        key0, key1 = min(i, A[i][j]), max(i, A[i][j])
        B[i][j] = taisen_dic[(key0, key1)]

#print(B)

nn = len(taisen)

G = [[] for i in range(nn)]



for i in range(n):
    for j in range(n-2):
        G[B[i][j]].append(B[i][j+1])

#print(G)

S = [[i, 0] for i in range(nn)]
D = [-1] * nn

dis = 0
while len(S) > 0 and dis <= nn:
    now = S.pop()
    now0 = now[0]
    dis = now[1]
    if dis > D[now0]:
        D[now0] = dis
        for i in G[now0]:
            S.append([i, dis+1])
            #print(S)

if dis > nn:
    print(-1)
else:
    print(max(D) + 1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

AA = [[j for j in i] for i in A]

ID = [[-1] * n for i in range(n)]
id_ = 0
for i in range(n):
    for j in range(i+1,n):
        ID[i][j] = id_
        ID[j][i] = id_
        id_ += 1

for i in range(n):
    for j in range(n-1):
        A[i][j] = ID[i][A[i][j]]

M = [[] for i in range(id_)]
IN = [0] * id_
for i in range(n):
    for j in range(n-2):
        M[A[i][j]].append(A[i][j+1])
        IN[A[i][j+1]] +=1
# print(A)
# print(M)

# 以下、トポロジカルソート

S = []
s = 0

for i in range(id_):
    if IN[i] == 0:
        S.append(i)

while s < len(S):
    for x in M[S[s]]:
        IN[x] -= 1
        # print(x,IN)
        if IN[x] == 0:
            S.append(x)
    s += 1

# print(S)

if len(S) < id_:
    print(-1)
else:
    T = [1] * id_
    for i in range(id_):
        for j in M[S[i]]:
            T[j] = max(T[j], T[S[i]] + 1)
    print(max(T))


# 以下、閉路検出(今は削除)

# V = [0] * id_
# S = [0]
# V[0] = 1

# import sys

# def visit(x):
#     if V[x] == 1:
#         print(-1)
#         sys.exit()
#     elif V[x] == 0:
#         V[x] = 1
#         for i in M[x]:
#             visit(i)
#         V[x] = 2

# for i in range(id_):
#     if V[i] == 0:
#         visit(i)
# print("heironasi")

# 閉路検出ここまで
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [[[''] * (310) for _ in range(310)] for _ in range(310)]
    def exp(i,j,k):
        if i + j + k == 0:
            return 0
        if dp[i][j][k]:
            return dp[i][j][k]
        ans = n
        if i > 0:
            ans += i * exp(i-1,j,k)
        if j > 0:
            ans += j * exp(i+1,j-1,k)
        if k > 0:
            ans += k * exp(i,j+1,k-1)
        ans /= (i+j+k)
        dp[i][j][k] = ans
        return ans

    ans = exp(a.count(1),a.count(2),a.count(3))
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter
import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[.0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(a[3]+1):
        for j in range(a[2]+a[3]-k+1):
            for i in range(n-j-k+1):
                if i + j + k == 0:
                    continue
                tmp = n
                if i > 0:
                    tmp += i * dp[i-1][j][k]
                if j > 0:
                    tmp += j * dp[i+1][j-1][k]
                if k > 0:
                    tmp += k * dp[i][j+1][k-1]
                dp[i][j][k] = tmp / (i+j+k)
    print(dp[a[1]][a[2]][a[3]])

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

N,K = map(int,input().split())
A = [int(x) for x in input().split()]
B = list(set(A))

C = []
for i in B:
  C.append([i,A.count(i)])

D = sorted(C,key=lambda x: x[1])

print(sum(x[1] for x in D[:-K:]))

### FIXED CODE ###

import collections

N,K = map(int,input().split())
A = [int(x) for x in input().split()]

B = sorted(list(collections.Counter(A).values()),reverse=True)

print(sum(B[K::]))
### BUGGY CODE ###

X,K,D = map(int,input().split())
X = abs(X)
if X-K*D>=0:
    print(X-K*D)
else:
    while(X > 0 and K > 0):
        K = K-1
        X = X-D
    if K % 2 == 0:
        print(abs(X))
    else:
        X = X+D
        print(X)

### FIXED CODE ###

X,K,D = map(int,input().split())
X = abs(X)
N = X//D
if N>K:
    N=K
X = X-N*D
K -= N
if K%2 == 0:
    print(X)
else:
    X -= D
    print(abs(X))
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

s = STR()
a = []
i = 0
while i < len(s):
    if s[i] == 'A':
        a.append(0)
        i += 1
    elif i < len(s) - 1 and s[i:i + 2] == 'BC':
        a.append(1)
        i += 2
    else:
        a.append(2)
        i += 1
debug(a)
ans = 0
flag = True
while flag:
    flag = False
    for i in reversed(range(1, len(a))):
        if a[i] == 1 and a[i - 1] == 0:
            ans += 1
            a[i], a[i - 1] = a[i  - 1], a[i]
            flag = True
print(ans)

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

s = STR()
a = []
i = 0
while i < len(s):
    if s[i] == 'A':
        a.append(0)
        i += 1
    elif i < len(s) - 1 and s[i:i + 2] == 'BC':
        a.append(1)
        i += 2
    else:
        a.append(2)
        i += 1
debug(a)
arr = []
bgn = -1
end = -1
for i in range(len(a)):
    if bgn == -1 and a[i] != 2:
        bgn = i
    if a[i] == 2 and end == -1:
        end = i
        arr.append(a[bgn:end])
        bgn = -1
        end = -1
arr.append(a[bgn:len(a) + 1])
debug(arr)
ans = 0
for b in arr:
    num0 = 0
    for i in b:
        if i == 0:
            num0 += 1
        if i == 1:
            ans += num0
print(ans)
### BUGGY CODE ###

'''
参考
https://marco-note.net/abc-175-work-log/
'''
N, K = map(int, input().split())        # コマ数、最大移動可能回数
P = list(map(int, input().split()))     # 移動先のコマ番号
C = list(map(int, input().split()))     # そのコマに立ち寄った時に加算される得点

ans = -float('inf')             # 解を-∞で初期化

for piece in range(N):          # 各コマについて、スタート地点とした場合の得点を調べる
    S = []                      # 累積和
    mov = P[piece] - 1          # 1回目の移動：移動先（indexなので-1する）
    S.append(C[mov])            # 1回目の移動：得点

    while mov != piece:             # 2回目以降の移動（スタート地点に戻ったらループ終了）
        mov = P[mov] - 1            # 2回目以降：移動先
        S.append(S[-1] + C[mov])    # 2回目以降：得点（最終要素に加算した値をリストに追加）
    
    if K <= len(S):             # 【パターン1】与えられた移動可能回数では一巡できない
        score = max(S[:K])      # 得点=移動可能回数までの最大得点
    elif S[-1] <= 0:            # 【パターン2】一巡できるが一巡してしまうと得点が減る
        score = max(S)          # 得点=一巡するまでの最大得点
    else:
        score_a = S[-1] * (K // len(S))     # 【パターン3-1】与えられた移動可能回数で廻れるだけ廻る
        rem = K % len(S)
        if rem != 0:
            score_a += max(0, max(S[:rem]))
        score_b = S[-1] * (K // len(S) - 1) # 【パターン3-2】1周少なく廻りあとは最高得点のところで止める
        score_b += max(S)
        score = max(score_a, score_b)
    
    ans = max(ans, score)

print(ans)

### FIXED CODE ###

'''
参考
https://marco-note.net/abc-175-work-log/
'''
N, K = map(int, input().split())        # コマ数、最大移動可能回数
P = list(map(int, input().split()))     # 移動先のコマ番号
C = list(map(int, input().split()))     # そのコマに立ち寄った時に加算される得点

ans = -float('inf')             # 解を-∞で初期化

for piece in range(N):          # 各コマについて、スタート地点とした場合の得点を調べる
    S = []                      # 累積和
    mov = P[piece] - 1          # 1回目の移動：移動先（indexなので-1する）
    S.append(C[mov])            # 1回目の移動：得点

    while mov != piece:             # 2回目以降の移動（スタート地点に戻ったらループ終了）
        mov = P[mov] - 1            # 2回目以降：移動先
        S.append(S[-1] + C[mov])    # 2回目以降：得点（最終要素に加算した値をリストに追加）
    
    if K <= len(S):             # 【パターン1】与えられた移動可能回数では一巡できない
        score = max(S[:K])      # 得点=移動可能回数までの最大得点
    elif S[-1] <= 0:            # 【パターン2】一巡できるが一巡してしまうと得点が減る
        score = max(S)          # 得点=一巡するまでの最大得点
    else:
        score_a = S[-1] * (K // len(S))     # 【パターン3-1】与えられた移動可能回数で廻れるだけ廻る
        rem = K % len(S)
        if rem != 0:
            score_a += max(0, max(S[:rem]))
        score_b = S[-1] * (K // len(S) - 1) # 【パターン3-2】1周少なく廻りあとは最高得点のところで止める
        score_b += max(S)
        score = max(score_a, score_b)
    
    ans = max(ans, score)

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

def e_all_you_can_eat():
    N, T = [int(i) for i in input().split()]
    Dishes = sorted([[int(i) for i in input().split()] for j in range(N)])

    # dp[i][j]: i 番目までの料理を j 分以内に完食できるように選んだとき、満足度の和の最大値
    dp = [[0] * (T + 1) for _ in range(N + 1)]
    ans = 0
    dp[0][0] = 0  # 食べていないときの満足度は 0 とする
    for i in range(1, N + 1):
        for j in range(T):
            dp[i][j] = dp[i - 1][j]  # i 番目を食べなかった場合

            # i 番目を食べることにした場合
            # (最後の料理は、ラストオーダー時刻が来ていなければ
            # 頼んで食いっぱなしにしてよいので、下の条件分岐と独立に考えてよい)
            ans = max(ans, dp[i][j] + Dishes[i - 1][1])

            # i 番目の料理を食べて j 分になることが可能なとき
            # (この条件を満たさないなら、i 番目の料理を食うと j 分以内に収まらない)
            if j - Dishes[i - 1][0] >= 0:
                dp[i][j] = max(dp[i][j],
                               dp[i - 1][j - Dishes[i - 1][0]] + Dishes[i - 1][1])
    return ans

print(e_all_you_can_eat())

### FIXED CODE ###

def e_all_you_can_eat():
    N, T = [int(i) for i in input().split()]
    Dishes = sorted([[int(i) for i in input().split()] for j in range(N)])

    # dp[i][j]: i 番目までの料理を j 分以内に完食できるように選んだとき、満足度の和の最大値
    dp = [[0] * (T + 1) for _ in range(N + 1)]
    ans = 0
    dp[0][0] = 0  # 食べていないときの満足度は 0 とする
    for i in range(1, N + 1):
        for j in range(T):
            dp[i][j] = dp[i - 1][j]  # i 番目を食べなかった場合

            # i 番目を食べることにした場合
            # (最後の料理は、ラストオーダー時刻が来ていなければ
            # 頼んで食いっぱなしにしてよいので、下の条件分岐と独立に考えてよい)
            ans = max(ans, dp[i][j] + Dishes[i - 1][1])

            # i 番目の料理を食べて j 分になることが可能なとき
            # (この条件を満たさないなら、i 番目の料理を食うと j 分以内に収まらない)
            if j - Dishes[i - 1][0] >= 0:
                dp[i][j] = max(dp[i][j],
                               dp[i - 1][j - Dishes[i - 1][0]] + Dishes[i - 1][1])
    return ans

print(e_all_you_can_eat())
### BUGGY CODE ###

N,M,K=map(int,input().split())
graph_data=[[0]*N for _ in range(N)]
block_data=[[0]*N for _ in range(N)]
    
for _ in range(M):
    i,j=map(int,input().split())
    graph_data[i-1][j-1]=graph_data[j-1][i-1]=1
for _ in range(K):
    i,j=map(int,input().split())
    block_data[i-1][j-1]=block_data[j-1][i-1]=1

from collections import deque

def bfs(start, W):
    work_queue = deque([])
    visited = set()
    work_queue.append(start)
    visited.add(start)
    while work_queue:
        here = work_queue.popleft()
        for i, node in enumerate(W[here]):
            if node ==0: continue
            if i not in visited:
                work_queue.append(i)
                visited.add(i)

    return visited

ans=[0]*N
for i in range(N):
    for j in bfs(i,graph_data):
        if i==j:continue
        if graph_data[i][j]==0:
            ans[i]+=1
        if block_data[i][j]==1:
            ans[i]-=1
pri=''
for i in range(N):
    pri+=str(ans[i])
    if i!=N-1:
        pri+=' '
print(pri)

### FIXED CODE ###

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

class UnionFind:
    def __init__(self, n):
        self.ps = [-1] * (n + 1)
 
    def find(self, x):
        if self.ps[x] < 0:
            return x
        else:
            self.ps[x] = self.find(self.ps[x])
            return self.ps[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.ps[x] > self.ps[y]:
            x, y = y, x
        self.ps[x] += self.ps[y]
        self.ps[y] = x
        return True
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def size(self, x):
        x = self.find(x)
        return -self.ps[x]

uf = UnionFind(N)
friends = [0]*(N+1)
chain = [0]*(N+1)


for _ in range(M):
    A, B = map(int, input().split())
    friends[A] += 1
    friends[B] += 1
    uf.union(A, B)

for _ in range(K):
    C, D = map(int, input().split())
    if uf.same(C, D):
        friends[C] += 1
        friends[D] += 1

ans = []

for i in range(1, N+1):
    ans.append(uf.size(i) - friends[i] - 1)

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

import sys
import os
import math
import bisect
import collections

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A, B, N = il()
    ret = 0
    mi = math.floor(B / N)
    for n in range(mi, N + 1):
        ret = max(ret, f(A, B, n))
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os
import math
import bisect
import collections
import itertools

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A, B, N = il()
    print(f(A, B, min(B - 1, N)))


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

N=int(input())
A = list(map(int,input().split()))
ans = []
for i in range(1,N+1):
    ans.append(A.index(i)+1)
print(*ans)

### FIXED CODE ###

N=int(input())
A = list(map(int,input().split()))
ans = []
for i,n in enumerate(A):
    ans.append((i+1,n))
ans.sort(key = lambda x:x[1])
for i,j in ans:
    print(i,end= ' ')
### BUGGY CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[float('inf')]*(N+1)
dp[0]=0
for i in range(N-1):
    for j in range(1,K+1):
        if i+j>N-1:
            break
        else:
            dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]))
print(dp[N-1])




### FIXED CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[float('inf')]*(N+1)
dp[0]=0
for i in range(N-1):
    for j in range(1,K+1):
        if i+j>N-1:
            break
        else:
            dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]))
print(dp[N-1])