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

import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from sys import stdin
from functools import reduce
sys.setrecursionlimit(4100000)
from functools import lru_cache
INF = 1 << 60

#ここから書き始める
n, m = map(int, input().split())
a = sorted(list(map(int, stdin.readline().split())))
x = [()] * m
for i in range(m):
    b, c = map(int, stdin.readline().split())
    x[i] = (c, b)
x.sort(reverse=True)
y = []
for i in range(m):
    z = [x[i][0]] * x[i][1]
    y.extend(z)
a += y
a.sort()
ans = 0
# print(a)
print(sum(a[len(a) - n:]))


### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)
  
for b,c in bc:
  a.extend([c]*b)
  if len(a) > n*2:
    break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

n = int(input())

print(0)
sex = input()
if sex == "Vacant":
    exit(0)
axis = sex

left = 1
right = n

while left + 1 < right:
    mid = (left + right) // 2
    print(mid)
    sex = input()
    if sex == "Vacant":
        exit(0)
    elif sex == axis:
        left = mid + 1
    else:
        right = mid

print(left)



### FIXED CODE ###

def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)
r_sex = val(n - 1)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != l_sex:
        right = mid
        r_sex = sex
    elif (mid - left) % 2 == 1 and sex == l_sex:
        right = mid
        r_sex = sex
    else:
        left = mid
        l_sex = sex

print(left, flush=True)
exit(0)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
s = input()
G = [[] for _ in range(2 * N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    if s[a] == s[b]:
        G[a].append(b + N)
        G[b].append(a + N)
    else:
        G[a + N].append(b)
        G[b + N].append(a)

status = [0] * (2 * N) #0 = 未訪問　1 = 訪問中 2 = 訪問済
def dfs(v):
    if status[v] == 1:
        print('Yes')
        exit()
    elif status[v] == 0:
        status[v] = 1
        for u in G[v]:
            dfs(u)
        status[v] = 2
    return None

for v in range(2 * N):
    dfs(v)
print('No')


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
s = input()
G = [[] for _ in range(2 * N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    if s[a] == s[b]:
        G[a].append(b + N)
        G[b].append(a + N)
    else:
        G[a + N].append(b)
        G[b + N].append(a)

status = [0] * (2 * N) #0 = 未訪問　1 = 訪問中 2 = 訪問済
def dfs(v):
    if status[v] == 1:
        print('Yes')
        exit()
    elif status[v] == 0:
        status[v] = 1
        for u in G[v]:
            dfs(u)
        status[v] = 2

for v in range(2 * N):
    dfs(v)
print('No')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
#input
N = int(input())
A = list(map(int, input().split()))
 
#output
from collections import Counter
 
l = Counter(A).most_common()
l = [b for a, b in l]
 
maximum_operation = [0] * N
for K in range(len(l)):
    l = Counter(A).most_common()
    l = [b for a, b in l]
    while l[K] > 0:
        for i in range(K+1):
            l[i] -= 1
        l.sort(reverse = True)
        maximum_operation[K] += 1
 
for m in maximum_operation:
    print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

#output
from collections import Counter
import bisect

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
p = sum(l)

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = sum(l[0:a]) 
    ll.append((b + c)/x)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)
### BUGGY CODE ###

aa=int(input())
N=[0 for i in range(aa)]
for i in range(aa):
  bb=input()
  #print(b)
  N[i]=bb.split()




for i in range(aa):

  a=int(N[i][0])
  b=int(N[i][1])
  c=int(N[i][2])
  d=int(N[i][3])

  e=a-a//b*b
  f=d-d//b*b
  

  h=0 #YES=0 NO=1


  if a<b or d<b :
    h=1
  else:

  
    if f!=0 :
      while e<b:
        if e>c :
          h=1
        e+=f
        #print(e)
        #print(f)
  #print("while")
    else:
      if e>c :
        h=1
        e+=f

  

  if h==1:
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

from fractions import gcd

for i in range(n):
    a = C[i][0]
    b = C[i][1]
    c = C[i][2]
    d = C[i][3]
    ng = 0

    e = 0  # 最初に補充が発生する直前の本数
    e0 = a - b
    e1 = ((c - a%b) // b) * b + a%b
    e = min(e0, e1)

    if e < 0 or b > d:
        ng = 1
    else:
        g = gcd(b, d)
        # print(c+1, b-1, g)
        if c+1 <= b-1 and (c - e) // g < (b-1 - e) // g:
            ng = 1

    if ng == 1:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

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

streaks = []
c = s[0]
i = 1
count = 1
while True:
    if i == n:
        streaks.append(count)
        count = 1
        break
    if s[i] == c:
        i += 1
        count += 1
    else:
        c = s[i]
        i += 1
        streaks.append(count)
        count = 1

start = s[0]
res = []
for i in range(len(streaks)):
    x = 0
    stop = min(len(streaks), i + 2 * k + start)
    for j in range(i, stop):
        x += streaks[j]
    res.append(x)
    start = 1 - start
print(max(res))

### FIXED CODE ###

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

streaks = []
c = s[0]
i = 1
count = 1
while True:
    if i == n:
        streaks.append(count)
        break
    if s[i] == c:
        i += 1
        count += 1
    else:
        streaks.append(count)
        c = s[i]
        i += 1
        count = 1

accs = [0]
for num in streaks:
    accs.append(accs[-1] + num)
if accs[-1] != n:
    accs.append(n)

flag = s[0] == '0'
res = []
for i in range(len(accs)):
    if flag:
        index = i + 2 * k
    else:
        index = i + 2 * k + 1
    index = min(index, len(accs) - 1)
    res.append(accs[index] - accs[i])
    flag = not flag

print(max(res))
### BUGGY CODE ###

n = input()
n = int(n)

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

l = []
for i, p in enumerate(pl[:-1]):
    l.append(max(pl[i+1:])-p)

m = max(l)
print(m)

### FIXED CODE ###

n = input()
n = int(n)

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

m = pl[0]
M = pl[0]
difM = pl[1]-pl[0]

for i, p in enumerate(pl[1:]):
    if p < m: 
        m = p
        continue
    if p - m > difM:
        difM = p - m

print(difM)
### BUGGY CODE ###

from collections import Counter
 
def verify_anagrams(first_word, second_word):
    def get_counter(s):
        return Counter(s.upper().replace(' ', ''))
 
    return get_counter(first_word) == get_counter(second_word)
flag=0
n=int(input())
list1=[]

for i in range(n):
    list1.append(input())
for i in range(n):
    for j in range(n):
        if i>j:
            if verify_anagrams(list1[i], list1[j]):
                flag=flag+1
print(flag)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
d = defaultdict(int)
 
for i in range(N):
    s = str(sorted(input()))
    d[s] += 1
ans = 0
 
for key in d.keys():
    ans += d[key]*(d[key]-1)//2
print(ans)
### BUGGY CODE ###

"""
考え方

N-1までの値を合計した値が答え
"""

N = int(input())

ans = 0
for i in range(1,N):
  ans += i

print(ans)

### FIXED CODE ###

N=int(input())

ans = N*(N-1)
ans //= 2

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

int1 = lambda x: int(x) - 1
import sys
sys.setrecursionlimit(1000000000)

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

start_point = set(range(N))
to_point = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int1, input().split())
    start_point = start_point - {y}
    to_point[x].append(y)

dp_memo = [-1]*N
for x in range(N):
    if len(to_point[x]) == 0:
        dp_memo[x] = 0

# 点i始点のLongest Pathの長さ
def dp(i):
    if dp_memo[i] >= 0:
        return dp_memo[i]
    lp = 0
    for j in to_point[i]:
        lp = max(lp, dp(j)+1)
    dp_memo[i] = lp
    return lp

for i in range(N):
    dp(i)

print(max(dp_memo))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

int1 = lambda x: int(x) - 1

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

to_point = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int1, input().split())
    to_point[x].append(y)

dp_memo = [-1]*N
for x in range(N):
    if len(to_point[x]) == 0:
        dp_memo[x] = 0

# 点i始点のLongest Pathの長さ
def dp(i):
    if dp_memo[i] >= 0:
        return dp_memo[i]
    lp = 0
    for j in to_point[i]:
        lp = max(lp, dp(j)+1)
    dp_memo[i] = lp
    return lp

for i in range(N):
    dp(i)

print(max(dp_memo))
### BUGGY CODE ###

n,m = map(int,input().split())
if m!=0:
    ls = [int(input()) for _ in range(m)]

else:
    ls = []

dp = [0 for _ in range(n+1)]
dp[0]=1

if 1 in ls:
    dp[1]= 0
else:
    dp[1]= 1

for i in range(2,n+1):
    if i in ls :
        dp[i] = 0
    else:
        dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)
        
print(dp[n]%(10**9+7))

### FIXED CODE ###

n,m = map(int,input().split())
ls = set()
for i in range(m):
    ls.add(int(input()))
dp = [0]*(n+1)
dp[0]=1
if 1 in ls:
    dp[1]= 0
else:
    dp[1]= 1
for i in range(2,n+1):
    if i in ls :
        continue
    dp[i] = dp[i-1]+dp[i-2]
print(dp[n]%(10**9+7))
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    INF = 10**12
    dp = [INF] * (N+1)
    dp[1] = 0
    for i in range(1,N):
        for j in range(1,min(K,N-i)+1):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i-1]-h[i+j-1]))
    print(dp[N])

if __name__ == "__main__":
    main()

### FIXED CODE ###

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

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

from collections import*

d=defaultdict(int)
db=defaultdict(int)

d[0]=0
db[0]=0

n,t=map(int,input().split())

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

dp=[]
dp2=[]
for time,value in x:
    for k,v in d.copy().items():
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        l.append(max(d[i],l[-1]))
    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in db.copy().items():
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        l.append(max(db[i],l[-1]))
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0
#print(dp2)
for i in range(len(dp)):
    for j in range(t):
#        print(ans,i)
        if i==0 or i==len(dp)-1:
            ans=max(dp[i][j]+dp2[i][t-j-1],ans)
        else:
#            print(i,t-j-1)
            dp2[i][t-j-1]
            ans=max(dp[i][j]+dp2[i][t-j-1]+x[i-1][1],ans)
    
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline   #input高速化 １文字の時の改行文字に注意+

d={i:0 for i in range(3001)}
db={i:0 for i in range(3001)}

n,t=map(int,input().split())

x=[tuple(map(int,input().split()))for i in n*[0]]
x.sort()
dp=[]
dp2=[]
for time,value in x:
    for k,v in d.copy().items():
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
        else:
            break
    l=[0]
    for i in range(1,t+1):
        if d[i]>l[-1]:
            l.append(d[i])
        else:
            l.append(l[-1])

    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in db.copy().items():
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
        else:
            break

    l=[0]
    for i in range(1,t+1):
        if db[i]>l[-1]:
            l.append(db[i])
        else:
            l.append(l[-1])
        
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0

for i in range(len(dp)):
    for j in range(t):
        if i==0 or i==len(dp)-1:
            tmp=dp[i][j]+dp2[i][t-j-1]
            if ans<tmp:
                ans=tmp
        else:
            tmp=dp[i][j]+dp2[i][t-j-1]+x[i-1][1]
            if tmp>ans:
                ans=tmp
print(ans)
### BUGGY CODE ###

n,k = map(int, input().split())
h_list = list(map(int, input().split()))
dp = [10**9]*n
dp[0] = 0
for i in range(1, n):
    dp[i] = min(dp[j]+ abs(h_list[i]-h_list[j]) for j in range(max(0,i-k),i))
print(dp[-1])

### FIXED CODE ###

n,k = map(int, input().split())
h_list = list(map(int, input().split()))
dp = [10**9]*n
dp[0] = 0
for i in range(1, n):
    for j in range(max(0,i-k),i):
        dp[i] = min(dp[i], dp[j] + abs(h_list[i]-h_list[j]))
print(dp[-1])
### BUGGY CODE ###

# Typical Stairs
import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    a = []
    a_ = a.append
    MOD = 10**9 + 7
    for i in range(m):
        a_(int(input()))

    if n == 1:
        print(1)
        exit()

    dp = [0 for i in range(n+1)]
    dp[0] = 1
    if 1 in a:
        dp[1] = 0
    else:
        dp[1] = 1

    for i in range(2, n + 1):
        if i in a:
            dp[i] = 0
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

    print(dp[-1])

if __name__ == '__main__':
    main()



### FIXED CODE ###

# Typical Stairs
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    n, m, *a = map(int, read().split())
    MOD = 10**9 + 7

    if n == 1:
        print(1)
        exit()

    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    is_broken = [False] * (n+1)
    for i in a:
        is_broken[i] = True
    if 1 in a:
        dp[1] = 0
    else:
        dp[1] = 1

    for i in range(2, n + 1):
        if is_broken[i]:
            continue
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

    print(dp[-1])

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

from collections import Counter
n=map(int, input().split())
*a,=map(int, input().split())
sa=Counter(a)

def fct(x):
    f1=[1]
    f2=[]
    for i in range(2,min(int(x**(1/2)+7),x)):
        if x%i==0:
            f1.append(i)
            f2.append(x//i)
    return (set(f1+f2))
ans=0
for ai in sa:
    if sa[ai]>1:
        continue
    fa=fct(ai)
    ad=True
    for f in fa:
        if f in sa and f!=ai:
            ad=False
            break
    if ad:
        ans+=1
print(ans)


### FIXED CODE ###

from collections import Counter
n=int(input())
*a,=map(int, input().split())
sa=Counter(a)

if 1 in sa:
    if sa[1]>1:
        print(0)
    else:
        print(1)
    exit()

# def fct(x):
#     f1=[1]
#     f2=[]
#     for i in range(2,min(int(x**(1/2)+7),x)):
#         if x%i==0:
#             f1.append(i)
#             f2.append(x//i)
#     return (set(f1+f2))
ans=0
for ai in sa:
    if sa[ai]>1:
        continue
    
    ans+=1
    if ai%2==0:
        for i in range(2,min(int(ai**(1/2)+7),ai)):
            if ai%i==0:
                if i in sa or ai//i in sa:
                    ans-=1
                    break
    else:
        for i in range(3,min(int(ai**(1/2)+7),ai),2):
            if ai%i==0:
                if i in sa or ai//i in sa:
                    ans-=1
                    break
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
#	ans = 10**20
#	for i in range(61):
#		for j in range(39):
#			if pow(2, i) * pow(3, j) > 10**19:
#				continue
#			for k in range(27):
#				if pow(2, i) * pow(3, j) * pow(5, k) > 10**19:
#					continue
#				for l in range(1, 6):
#					g = abs(n - l * pow(2, i) * pow(3, j) * pow(5, k))
#					res = a*i + b*j + c*k + (g+l) * d
#					ans = min(ans, res)
#	print(ans)
	dp = dict()
	dp[n] = 0

	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	def dfs(x):
		if x == 0:
			return
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add((x+1)//2, v):
				dfs((x+1)//2)

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				dfs(x//3+1)

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				dfs(x//5+1)
		return
	dfs(n)
	print(dp[0])

### FIXED CODE ###

import sys
from heapq import heappush, heappop
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
	dp = dict()
	dp[n] = 0
	q = [(0, n)]
	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	while True:
		l = heappop(q)
		if l[1] == 0:
			break
		x = l[1]
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add(x//2+1, v):
				heappush(q, (v, x//2+1))

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				heappush(q, (v, x//3+1))

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				heappush(q, (v, x//5+1))

	print(dp[0])
### BUGGY CODE ###

def main():
    N=int(input())
    a=[0]+list(map(int,input().split()))+[0]
    cost=[]
    for i in range(N+1):
        cost.append(abs(a[i+1]-a[i]))
    for i in range(N):
        print(sum(cost)-cost[i]-cost[i+1]+abs(a[i+2]-a[i]))
main()

### FIXED CODE ###

N=int(input())
a=[0]+list(map(int,input().split()))+[0]
cost=[]
for i in range(N+1):
    cost.append(abs(a[i+1]-a[i]))
S = sum(cost)
for i in range(N):
    print(S-cost[i]-cost[i+1]+abs(a[i+2]-a[i]))
### BUGGY CODE ###

N = int(input())
S = []
num = []
num_list = []
count_list = []
num_list_counter = 0
count = 0

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

for i in range(N):
    S.append(input())
    num = 1
    num *= pow_k(2, S[i].count('a'))
    num *= pow_k(3 , S[i].count('b'))
    num *= pow_k(5 , S[i].count('c'))
    num *= pow_k(7 , S[i].count('d'))
    num *= pow_k(11 , S[i].count('e'))
    num *= pow_k(13 , S[i].count('f'))
    num *= pow_k(17 , S[i].count('g'))
    num *= pow_k(19 , S[i].count('h'))
    num *= pow_k(23 , S[i].count('i'))
    num *= pow_k(29 , S[i].count('j'))
    num *= pow_k(31 , S[i].count('k'))
    num *= pow_k(37 , S[i].count('l'))
    num *= pow_k(41 , S[i].count('m'))
    num *= pow_k(43 , S[i].count('n'))
    num *= pow_k(47 , S[i].count('o'))
    num *= pow_k(73 , S[i].count('p'))
    num *= pow_k(79 , S[i].count('q'))
    num *= pow_k(83 , S[i].count('r'))
    num *= pow_k(89 , S[i].count('s'))
    num *= pow_k(97 , S[i].count('t'))
    num *= pow_k(101 , S[i].count('u'))
    num *= pow_k(103 , S[i].count('v'))
    num *= pow_k(107 , S[i].count('w'))
    num *= pow_k(109 , S[i].count('x'))
    num *= pow_k(113 , S[i].count('y'))
    num *= pow_k(127 , S[i].count('z'))

    if num_list_counter == 0:
        num_list.append(num)
        count_list.append(1)
        num_list_counter += 1
    else:
        judge = 0
        for j in range(num_list_counter):
            if num_list[j] == num:
                judge = 1
                count += count_list[j]
                count_list[j] += 1
        if judge == 0:
            num_list_counter += 1
            num_list.append(num)
            count_list.append(1)

print(count)


### FIXED CODE ###

N = int(input())
S = []
count = 0

dic = {}
for i in range(N):
    S.append(input())
    S[i] = sorted(S[i])
    S[i] = ''.join(S[i])
    if dic.setdefault(S[i], 0) > 0:
        count += dic[S[i]]
        dic[S[i]] += 1
    else:
        dic[S[i]] = 1
print(count)
### BUGGY CODE ###

N=int(input())
A=[int(i) for i in input().split()]
B=[[A[i],-10**15] for i in range(2**N)]
for i in range(N):
    for b in range(2**N):
        if ((1&(b>>i))==1):
            merge=B[b]+B[b^(1<<i)]
            merge.sort(reverse=True)
            B[b]=merge[:2]
ans=-10**15
for i in range(1,2**N):
    ans=max([ans,sum(B[i])])
    print(ans)


### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
B=[[A[i],-10**15] for i in range(2**N)]
for i in range(N):
    for b in range(2**N):
        if ((1&(b>>i))==1):
            merge=B[b]+B[b^(1<<i)]
            merge.sort(reverse=True)
            B[b]=merge[:2]
ans=-10**15
for i in range(1,2**N):
    ans=max([ans,sum(B[i])])
    print(ans)
### BUGGY CODE ###

INF = float('inf')
ans = INF
L, R = map(int, input().split())
for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
        ans = min(ans, i * j % 2019)
print(ans)

### FIXED CODE ###

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

h,w,d = map(int,input().split())
HW = [list(map(int,input().split())) for _ in range(h)]

q = int(input())
a = []
c = []
for i in range(q):
    L,R = map(int,input().split())
    b = list(range(L,R+1,d))
    
    x = 0
    for hw in HW:
        y = 0
        for num in hw:
            if num in b:
                c.append([num,[x+1,y+1]])
            y += 1
        x += 1
    c.sort()
    
    total = 0
    for j in range(len(b)-1):
        total += abs(c[j+1][1][0] - c[j][1][0]) + abs(c[j+1][1][1] - c[j][1][1])        
        
    print(total)

### FIXED CODE ###

h,w,d = map(int,input().split())
hw = [[] for _ in range(h*w+1)]
for i in range(h):
    row = list(map(int,input().split()))
    for j in range(w):
        hw[row[j]] = [i,j]
 
a = [0 for _ in range(h*w+1)]
for i in range(d+1,h*w+1):
    a[i] = a[i-d] + abs(hw[i][0] - hw[i-d][0]) + abs(hw[i][1] - hw[i-d][1])
 
q = int(input())
for i in range(q):
    L,R = map(int,input().split())
    print(a[R] - a[L])
### BUGGY CODE ###

from math import floor

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


ans = - 10 ** 9

for i in range(1, n+1):
    m = floor(a*i/b) - a*floor(i/b)
    ans = max(ans, m)
    
print(ans)

### FIXED CODE ###

from math import floor

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

if a == 1 or b == 1:
    print(0)
elif n < b:
    print(floor(a*n/b))
else:
    print(floor(a*(b-1)/b))