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

n,m=map(int,input().split())
first=[]
second=[]
ans="IMPOSSIBLE"
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        if bi in second:
            ans="POSSIBLE"
            break
        else:
            first.append(bi)
    elif bi==n:
        if ai in first:
            ans="POSSIBLE"
            break
        else:
            second.append(ai)
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
check=[0]*n
ans="IMPOSSIBLE"
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        if check[bi-1]==1:
            ans="POSSIBLE"
            break
        else:
            check[bi-1]+=1
    elif bi==n:
        if check[ai-1]==1:
            ans="POSSIBLE"
            break
        else:
            check[ai-1]+=1
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
lst = list(map(int,input().split()))
dp = [float('inf')]*n
dp[0] = 0
for i in range(1, min(k, len(lst))):
    dp[i] = abs(lst[i] - lst[0])
for i in range(k, n):
    for j in range(1, k+1):
        dp[i] = min(dp[i], dp[i-j]+abs(lst[i]-lst[i-j]))
print(dp[-1])

### FIXED CODE ###

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

dp = [float('inf')]*n
dp[0] = 0
for i in range(1, min(k, len(lst))):
    dp[i] = abs(lst[i] - lst[0])
for i in range(k, n):
    for j in range(1, k+1):
        dp[i] = min(dp[i], dp[i-j]+abs(lst[i]-lst[i-j]))
print(dp[-1])
### BUGGY CODE ###

import sys
N,K = map(int,sys.stdin.readline().split())
h = list(map(int,input().split()))
dp = [0]+[float('inf')]*(N-1)

for i in range(1,N):
  
  for j in range(max(0,i-K),i):
    dp[i] = min(dp[i],abs(h[i]-h[j])+dp[j])
    

print(dp[-1])

### FIXED CODE ###

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

S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d *= 10%mod
  p[r] += 1

#p.append(0)
#ans = 0
#c = Counter(p)
#for k,n in c.most_common():
#  if n > 1:
#    ans += 1
#  else:break
  
print(sum([i*(i-1)//2 for i in p]))


### FIXED CODE ###

S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1

print(sum([i*(i-1)//2 for i in p]))
### BUGGY CODE ###

N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {i: [set(), False] for i in range(1, N+1)}
    for i, j in links:
        d[i][0].add(j)
        d[j][0].add(i)
    b = len(d[1][0])
    if K - 1 < b:
        print(0)
    else:
        ans = K * perm(K - 1, b)
        d[1][1] = True
        root = d[1][0]
        a = K - 2
        while True:
            children = set()
            for i in list(root):
                d[i][1] = True
                b = len(d[i][0]) - 1
                if a < b:
                    print(0)
                    break
                children |= d[i][0]
                if b == 0:
                    continue
                ans *= perm(a, b)
            else:               
                for i in list(children):
                    if d[i][1]:
                        children.remove(i)
                if len(children) == 0:
                    print(ans % mod)
                    break
                root = children
                continue
            break

### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)
### BUGGY CODE ###

from scipy.special import comb
x,y = map(int,input().split())
a=2*x-y
b=2*y-x
if a%3!=0 or a<0 or b%3!=0 or b<0:
  print(0)
else:
  print(comb((a+b)//3,b//3,exact=True)%(10**9+7))

### FIXED CODE ###

def nCr(n, r, mod):
    x, y = 1, 1
    for i in range(1, r+1):
        x = x*(n+1-i)%mod
        y = y*i%mod
    return x*pow(y, mod-2, mod)%mod
a,b = map(int,input().split())
s=2*a-b
t=2*b-a
if s%3!=0 or s<0 or t%3!=0 or t<0:
  print(0)
else:
  print(nCr((s+t)//3,(t//3),10**9+7))
### BUGGY CODE ###

n = int(input())
x = int(input(),2)

def popcount2(n):
    return bin(n).count("1")

def popcount(n):
    ans = 0
    while n:
        ans += n % 2
        n //= 2
    return ans

pops = popcount(x)
x_pop_p = x%(pops + 1)
try:
    x_pop_m = x%(pops - 1)
except:
    x_pop_m = 0
for i in reversed(range(0,n)):
    bit = x^(1<<i)
    if bit == 0:
        print(0)
        continue
    if x&(1<<i):
        tmp = (x_pop_m - pow(2,i,(pops - 1)))%(pops - 1)
    else:
        tmp = (x_pop_p + pow(2,i,(pops + 1))) % (pops + 1)
    if tmp == 0:
        print(1)
        continue
    cnt = 2
    if tmp == 0:
        print(cnt-1)
        continue
    tmp = tmp % popcount(tmp)
    while tmp > 0:
        cnt += 1
        if tmp == 0:
            print(cnt-1)
            continue
        tmp %= popcount(tmp)
    print(cnt)

### FIXED CODE ###

n = int(input())
s = input()
x = int(s, 2)
pcx = s.count("1")
pc1 = x % (pcx - 1) if pcx > 1 else 0
pc2 = x % (pcx + 1)

def f(j):
    cnt = 0
    while j:
        j %= bin(j).count("1")
        cnt += 1
    return cnt

for i, y in enumerate(s):
    k = n - 1 - i
    if y == "0":
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)
### BUGGY CODE ###

import math

n = int(input())
answer = 0
for a in range(1,n+1):
    for b in range(1,n+1):
        for c in range(1,n+1):
            answer += math.gcd(a, math.gcd(b,c))
print(answer)

### FIXED CODE ###

import math

n = int(input())
answer = 0

for a in range(1,n+1):
    for b in range(1,n+1):
        t = math.gcd(a,b)
        for c in range(1,n+1):
            answer += math.gcd(t,c)
print(answer)
### BUGGY CODE ###

from functools import lru_cache
import sys
input = sys.stdin.readline

# sys.setrecursionlimit(100000)


def main():
    N, W = [int(i) for i in input().strip().split()]
    items = [[int(i) for i in input().strip().split()] for _ in range(N)]

    @lru_cache(None)
    def knapsack(capacity, value, idx):
        if idx < 0:
            return value
        if items[idx][0] > capacity:
            return knapsack(capacity, value, idx - 1)
        else:
            return max(
                knapsack(capacity, value, idx - 1),
                knapsack(capacity - items[idx][0],
                         value + items[idx][1], idx - 1)
            )

    return knapsack(W, 0, N-1)


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

class Solver():
    def __init__(self, N, W, items):
        self.N = N
        self.W = W
        self.items = items

    def solve(self):
        dp = [[0 for _ in range(self.W+1)] for _ in range(self.N+1)]
        for i in range(self.N):
            for w in range(self.W+1):
                if w - self.items[i][0] >= 0:
                    dp[i+1][w] = max(dp[i+1][w], dp[i][w - self.items[i][0]] + self.items[i][1])

                dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
        return dp[self.N][self.W]


def main():
    N, W = [int(i) for i in input().split()]
    items = [[int(i) for i in input().split()] for _ in range(N)]
    solver = Solver(N, W, items)
    print(solver.solve())


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

# -*- coding: utf-8 -*-
 
# t, s = map(str,input().split())

n = int(input())
str_a = input().split()

a = []
for i in range(len(str_a)):
    a.append(int(str_a[i]))

total = 0
for i in range(n):
    for j in range(i + 1, n):
        total += a[i] * a[j]

print(total % (1000000000 + 7))

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
# t, s = map(str,input().split())

n = int(input())
str_a = input().split()

a = []
for i in range(len(str_a)):
    a.append(int(str_a[i]))

total = 0
c = 0
for i in range(n - 1):
    c += a[-i]
    total += c * a[-(i + 1)]

print(total % (1000000007))
### BUGGY CODE ###

N,K=map(int,input().split())
c=0
for i in range(1,N+1):
    ans=[0,0,0]
    for j in range(1,2*N//K+1):
        if 1<=j*K-i<=N:
            for l in range(1,2*N//K+1):
                if 1<=l*K-j*K+i<=N and (2*i+l*K-j*K)%K==0:
                    count=0
                    ans[0]=i
                    ans[1]=j*K-i
                    ans[2]=l*K-j*K+i
                    ans.sort()
                    c+=1
print(c)

### FIXED CODE ###

from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
N,K=map(int,input().split())
if K%2==0:
    print((N//K)**3+(((N-K//2)//K+1)**3))
else:
    print((N//K)**3)
### BUGGY CODE ###

n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))

for i in range(m):
    if t[i] not in d:
        print('NO')
        break
    else:
        d.remove(t[i])
else:
    print('YES')

### FIXED CODE ###

from collections import Counter
n=int(input())
d=Counter(map(int,input().split()))
m=int(input())
t=Counter(map(int,input().split()))
for i in t.keys():
    if d[i]<t[i]:
        print('NO')
        break
else:
    print('YES')
### BUGGY CODE ###

N=int(input())

for i in range(1,N+1):
    count=0
    for x in range(1,i+1):
        if x**2>=i:break
        for y in range(1,N-(x**2)+1):
            if x**2+y**2+x*y>=i:break
            for z in range(1,N-(x**2+y**2)+1):
                if x**2+y**2+z**2+x*y+y*z+x*z==i:count+=1
                if x**2+y**2+z**2+x*y+y*z+x*z>i:break
    print(count)

### FIXED CODE ###

N=int(input())
dic={}
for i in range(1,N+1):
    dic[i]=0
for x in range(1,int(N**0.5)):
    for y in range(1,N-x**2):
        for z in range(1,N-(x**2+y**2+x*y)):
            if x**2+y**2+z**2+x*y+x*z+y*z>N:break
            if x**2+y**2+z**2+x*y+x*z+y*z in dic:
                dic[x**2+y**2+z**2+x*y+x*z+y*z]+=1


for i in range(1,N+1):
    print(dic[i])
### BUGGY CODE ###

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

cnt = 0

for i in range(N+1):
    for j in range(N+1):
        for k in range(N+1):
            if i*R + j*G + k*B == N:
                cnt += 1
print(cnt)
    

### FIXED CODE ###

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

cnt = 0

li = [R, G, B]
li = sorted(li)

_i = N//li[2]
for i in range(_i+1):
    _j = (N - li[2]*i )//li[1]
    for j in range(_j + 1):
        if (N - i*li[2] -  j*li[1])%li[0] == 0:
            cnt += 1

print(cnt)
### BUGGY CODE ###

def main():
    n = int(input())

    repo = []
    for i in range(n):
        command, acgt = input().split()
        if command[0] == 'i':
            if acgt not in repo:
                repo.append(acgt)
        elif command[0] == 'f':
            if acgt in repo:
                print('yes')
            else:
                print('no')
    return


main()


### FIXED CODE ###

import sys

def main():
    lines = sys.stdin.readlines()
    n = int(lines[0])

    repo = {}
    for i in range(1, n + 1):
        command, acgt = lines[i].split()
        if command[0] == 'i':
            if acgt not in repo:
                repo[acgt] = 0
        elif command[0] == 'f':
            if acgt in repo:
                print('yes')
            else:
                print('no')
    return


main()
### BUGGY CODE ###

k , s = map(int, input().split())

ans = 0

for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x + y + z == s:
        ans += 1
        
print(ans)

### FIXED CODE ###

k , s = map(int, input().split())

ans = 0

for x in range(k+1):
  for y in range(k+1):
      if s-x-y <= k and s-x-y>=0:
        ans += 1
        
print(ans)
### BUGGY CODE ###

N, A = map(int, input().split())
d = [x-A for x in list(map(int, input().split()))]
n = d.count(0)
d = [x for x in d if x != 0]
d.sort()
if not d:
	print(2**n - 1)
else:
	stack = []
	stack.append([0,0])
	stack.append([0,d[0]])
	ans = 0
	while stack:
		(pos, s) = stack.pop()

		if s == 0 and pos == len(d) - 1:
			ans += 1
		elif pos < len(d) - 1 and s <= 0:
			stack.append([pos+1,s])
			stack.append([pos+1,s + d[pos+1]])
	ans = ans * 2 ** n -1
	print(ans)

### FIXED CODE ###

N, A = map(int, input().split())
y = [int(i) - A for i in input().split()]
y = [0] + y
X = max(max(y) + A,A)
dp = []
for i in range(N+1):
	dp.append([])
	for j in range(2*N*X+1):
		if i == 0 and j == N*X:
			dp[i].append(1)
		elif i >= 1 and (j - y[i] < 0 or j - y[i] > 2*N*X):
			dp[i].append(dp[i-1][j])
		elif i >= 1 and 0 <= j - y[i] and j - y[i] <= 2*N*X:
			dp[i].append(dp[i-1][j]+dp[i-1][j-y[i]])
		else:
			dp[i].append(0)
print(dp[N][N*X]-1)
### BUGGY CODE ###

q = int(input())
for _ in [0]*q:
    s1, s2 = input(), input()
    l1, l2 = len(s1), len(s2)

    dp = [[0]*(l2+1) for _ in [0]*(l1+1)]
    for i, (c1, prev, cur) in enumerate(zip(s1, dp, dp[1:]), start=1):
        for j, (c2, ul, u, l, c) in enumerate(zip(s2, prev, prev[1:], cur, cur[1:]), start=1):
            dp[i][j] = max(ul+(c1==c2), u, l, c)

    print(dp[-1][-1])


### FIXED CODE ###

def lcs_hs(s1, s2):
    from bisect import bisect_left

    s2, lis, result = s2[::-1], [], 0
    find, append = s2.find, lis.append

    for c in s1:
        i = find(c)+1
        while i:
            j = bisect_left(lis, -i)
            if j >= result:
                append(-i)
                result += 1
            else:
                lis[j] = -i
            i = find(c, i)+1

    return result


print(*(lcs_hs(input(), input()) for _ in [0]*int(input())), sep="\n")
### BUGGY CODE ###

N = int(input())
S = input()

r = S.count('R')
g = S.count('G')
b = S.count('B')

ans = r*g*b

for i in range(0,N):
  for j in range(i,N):
    k = 2*j - i
    if j < k <= N-1:
      if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
        ans -= 1

print(ans)













### FIXED CODE ###

N = int(input())
S = list(input())

r = S.count('R')
g = S.count('G')
b = S.count('B')

ans = r*g*b

for i in range(0,N):
  for j in range(i,N):
    k = 2*j - i
    if j < k <= N-1:
      if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
        ans -= 1

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

n = int(input())
l_li = [int(x) for x in input().split()]

count = 0

for i in range(n):
  for j in range(i+1,n):
    a = l_li[i]
    b = l_li[j]
    wa = a + b
    sa = a - b
    if sa < 0:
      sa = -1 * sa
    target = l_li[j+1:]
    count += sum([sa<x<wa for x in target])
print(count)

### FIXED CODE ###

import bisect
n = int(input())
l_li = [int(x) for x in input().split()]
l_li.sort()

count = 0
  
for i in range(n):
  for j in range(i+1,n):
    wa = l_li[i] + l_li[j]
    count += bisect.bisect_left(l_li, wa) - j - 1
    
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
 
 
def solve(ins):
    n, k, *h = map(int, ins.split())
    costs = [0]
    for i in range(1, n):
        cost = min(costs[-j] + abs(h[i] - h[i - j]) for j in range(1, min(i, k) + 1))
        costs.append(cost)
    return costs[-1]
 
 
if __name__ == "__main__":
    print(solve("\n".join([input(), input()])))

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def solve(ins):
    n, k, *h = map(int, ins.split())
    costs = [0]
    for i in range(1, n):
        cost = min([costs[-j] + abs(h[i] - h[i - j]) for j in range(1, min(i, k) + 1)])
        costs.append(cost)
    return costs[-1]


if __name__ == "__main__":
    print(solve("\n".join([input(), input()])))
### BUGGY CODE ###

import math


def main():
    """
    H * W 板チョコ3分割
    面積：A B C
    minimize(max(A B C) - min(A B C))

    縦or横がMAX、片方が途中まで
    上記1つと、残りを半分
    残り：面積２以上
    """
    H, W = list(map(int, input().strip().split()))
    # 縦MAX, H>=2より、W-1まで確認
    # 横MAX, H>=2より、W=1のとき３分割できないので、W>=2
    answer = calc_answer(H, W)
    answer = calc_answer(W, H, answer=answer)
    print(answer)


def calc_answer(H, W, answer=None):
    if answer is None:
        answer = float("inf")

    for _w in range(1, math.ceil(W / 2) + 1):
        # 縦MAXで試す
        S = [
            H * _w,
            H * math.ceil((W - _w) / 2),
            H * int((W - _w) // 2),
        ]
        if not 0 in S:
            S_diff = max(S) - min(S)
            #print(H, _w, S, S_diff, answer, sep="\t")
            answer = min(answer, S_diff)

        # 横MAXで縦分割
        for _h in range(1, math.ceil(H / 2) + 1):
            S = [
                H * _w,
                (W - _w) * _h,
                (W - _w) * (H - _h),
            ]
            if not 0 in S:
                S_diff = max(S) - min(S)
                #print(_h, _w, S, S_diff, answer, sep="\t")
                answer = min(answer, S_diff)

    return answer

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math


def main():
    """
    H * W 板チョコ3分割
    面積：A B C
    minimize(max(A B C) - min(A B C))

    縦or横がMAX、片方が途中まで
    上記1つと、残りを半分
    残り：面積２以上
    """
    H, W = list(map(int, input().strip().split()))
    # 縦MAX, H>=2より、W-1まで確認
    # 横MAX, H>=2より、W=1のとき３分割できないので、W>=2
    answer = calc_answer(H, W)
    answer = calc_answer(W, H, answer=answer)
    print(answer)


def calc_answer(H, W, answer=None):
    if answer is None:
        answer = float("inf")

    for _w in range(1, math.ceil(W / 2) + 1):
        # 縦MAXで試す
        S = [
            H * _w,
            H * math.ceil((W - _w) / 2),
            H * int((W - _w) // 2),
        ]
        if not 0 in S:
            S_diff = max(S) - min(S)
            #print(H, _w, S, S_diff, answer, sep="\t")
            answer = min(answer, S_diff)

        # 横MAXで縦分割
        S = [
            H * _w,
            (W - _w) * math.ceil(H / 2),
            (W - _w) * int(H // 2),
        ]
        if not 0 in S:
            S_diff = max(S) - min(S)
            #print(_h, _w, S, S_diff, answer, sep="\t")
            answer = min(answer, S_diff)

    return answer

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

def Solve(c,s):
    if s:
        if max(c)>4:return False
        for i in range(9):
            if c[i]>=2:
                cc=c[:]
                cc[i]-=2
                if Solve(cc,False):return True
    else:
        check=0
        for i in range(4):check+=c.count(3*i)
        if check==9:return True
        else:
            for i in range(7):
                if c[i]>=1:
                    cc=c[:]
                    for j in range(3):
                        cc[i+j]-=1
                        if cc[i+j]<0:break
                    if Solve(cc,False):return True
_in=""
while True:
    ans=[]
    try:_in=input()
    except EOFError:break
    for i in range(9):
        l=(_in+str(i+1))[::1]
        count=[l.count(str(j+1))for j in range(9)]
        if Solve(count,True):ans.append(str(i+1))
    print(0 if len(ans)==0 else " ".join(ans))

### FIXED CODE ###

def Solve(c,s):
    if s:
        if max(c)>4:return False
        for i in range(9):
            if c[i]>=2:
                cc=c[:]
                cc[i]-=2
                if Solve(cc,False):return True
    else:
        check=0
        for i in range(4):check+=c.count(3*i)
        if check==9:return True
        else:
            for i in range(7):
                if c[i]>=1:
                    cc=c[:]
                    isneg=False
                    for j in range(3):
                        cc[i+j]-=1
                        if cc[i+j]<0:
                            isneg=True
                            break
                    if isneg==False and Solve(cc,False):return True
_in=""
while True:
    ans=[]
    try:_in=input()
    except EOFError:break
    for i in range(9):
        l=(_in+str(i+1))[::1]
        count=[l.count(str(j+1))for j in range(9)]
        if Solve(count,True):ans.append(str(i+1))
    print(0 if len(ans)==0 else " ".join(ans))
### BUGGY CODE ###

# F - Strivore

K = int(input())
S = list(str(input()))
N = len(S)
MOD = 10**9+7

fac = [1, 1]
inv = [0, 1]
finv = [1, 1]

for i in range(2, N+K+1):
    fac.append(fac[-1] * i % MOD)
    inv.append(MOD - inv[MOD%i] * (MOD//i) % MOD)
    finv.append(finv[-1] * inv[-1] % MOD)

def comb_mod(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m

ans = 0
for i in range(K+1):
    tmp = pow(25, i, MOD)
    tmp *= comb_mod(i+N-1, N-1, MOD)
    tmp *= pow(26, K-i, MOD)
    ans += tmp
    ans %= MOD
print(ans)



### FIXED CODE ###

# F - Strivore

K = int(input())
S = list(str(input()))
N = len(S)
MOD = 10**9+7

fac = [1, 1]
inv = [0, 1]
finv = [1, 1]

for i in range(2, N+K+1):
    fac.append(fac[-1] * i % MOD)
    inv.append(MOD - inv[MOD%i] * (MOD//i) % MOD)
    finv.append(finv[-1] * inv[-1] % MOD)

def comb_mod(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m

ans = 0
for i in range(K+1):
    tmp = pow(25, i, MOD)
    tmp *= comb_mod(i+N-1, N-1, MOD)
    tmp *= pow(26, K-i, MOD)
    ans += tmp
    ans %= MOD
print(ans)
### BUGGY CODE ###

# 2019-11-16 14:51:41(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    job_list = []
    for _ in range(n):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        if a <= m:
            job_list.append(tuple([a, b]))

    job_list.sort(reverse=True, key=lambda x: x[1])
    rewards = [0 for _ in range(m+1)]
    count = 0
    for i in range(len(job_list)):
        if 0 in rewards[job_list[i][0]:]:
            rewards[rewards.index(0, job_list[i][0])] = job_list[i][1]
            count += 1
            if count == m:
                break
    
    print(sum(rewards))
    

if __name__ == "__main__":
    main()


### FIXED CODE ###

# 2019-11-16 14:51:41(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 
import heapq

def main():
    # 10**5連勤とか超人すぎる
    n, m = [int(x) for x in sys.stdin.readline().split()]

    job_list = dict((i, list()) for i in range(1, m+1))
    for _ in range(n):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        if a <= m:
            job_list[a].append(b)
    
    schedule = [0 for _ in range(m+1)] # 当日は報酬0
    q = []
    for i in range(1, m+1):
        for reward in job_list[i]: # 期限i日前にできる仕事の報酬一覧をheqp queueに入れる
            heapq.heappush(q, -reward) 
            # あとで最大値を取り出すために-1かける(heappop()で取り出せるのは最小値)

        if q: # その日できる仕事が一つでもあれば
            # 報酬の最小値(マイナスなので元々の最大値)を取り出して-1をかけ、scheduleにいれる
            schedule[i] = -heapq.heappop(q) # 戻り値を返すと同時にq自体も変更している
        else: # できる仕事がなければ
            pass  # その日の報酬は0のまま

    print(sum(schedule))


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

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

def LI(): return list(map(int, stdin.readline().split()))
def LS(): return list(stdin.readline())

a,b,n = LI()
import math

ans = 0
for i in range(n+1):
    m = math.floor(a*i/b)-a*math.floor(i/b)
    if m>ans:
        ans = m
print(ans)

### FIXED CODE ###

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

def LI(): return list(map(int, stdin.readline().split()))
def LS(): return list(stdin.readline())

a,b,n = LI()

m = min(b-1, n)
print(int(a*m/b)-a*int(m/b))