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

# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


mod = 10 ** 9 + 7
N, M = list(map(int, input().split()))
A = [0]*N
B = [0]*N
# 日数別にもらえる額を管理
# money = defaultdict(list)
keys = list(range(1, 1+10**5))
# print(keys)
values = [[] for i in range(1, 1+10**5)]
job = dict(zip(keys, values))
for i in range(N):
    a, b = map(int, input().split())
    job[a].append(b)
    # A[i], B[i] = a, b
# A日後にB円もらえる、M日後に報酬最大化
ans = 0
can_work = []
for delay in range(1, 1+M):
    can_work.extend(job[delay])
    # print('delay', delay)
    # print(job)
    if (len(can_work) != 0):
        max_money = max(can_work)
        ans += max_money
        can_work.remove(max_money)

    # for i in range(delay):
    #     print(delay-i)
    #     if len(jpb[delay-i]) != 0:
    #         print('found')
    #         max_money = max(jpb[delay-i])
    #         ans += max_money
    #         jpb[delay-i].remove(max_money)
    #         jpb[delay-i]
    #         break
    #     print('===========')
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


mod = 10 ** 9 + 7
N, M = list(map(int, input().split()))
A = [0]*N
B = [0]*N
# 日数別にもらえる額を管理
# money = defaultdict(list)
keys = list(range(1, 1+10**5))
# print(keys)
values = [[] for i in range(1, 1+10**5)]
job = dict(zip(keys, values))
for i in range(N):
    a, b = map(int, input().split())
    job[a].append(-b)
    # A[i], B[i] = a, b
# A日後にB円もらえる、M日後に報酬最大化
ans = 0
can_work = []
heapq.heapify(can_work)
for delay in range(1, 1+M):
    for item in job[delay]:
        heapq.heappush(can_work, item)
    # print('delay', delay)
    # print(job)
    if (len(can_work) != 0):
        ans -= heapq.heappop(can_work)

    # for i in range(delay):
    #     print(delay-i)
    #     if len(jpb[delay-i]) != 0:
    #         print('found')
    #         max_money = max(jpb[delay-i])
    #         ans += max_money
    #         jpb[delay-i].remove(max_money)
    #         jpb[delay-i]
    #         break
    #     print('===========')
print(ans)
### BUGGY CODE ###

from numba import jit
import numpy as np

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

# for _ in range(min(k,int(math.log(n,2)))):

@jit
def solve():
    for _ in range(k):
        start=[0]*n
        end=[0]*n
        
        for i in range(n):
            start[max(0,i-A[i])]+=1
            end[min(n-1,i+A[i])]+=1
    
        # update ans
        cnt=0
        for i in range(n):
            cnt+=start[i]
            A[i]=cnt
            cnt-=end[i]
        if A[0]==n and A[-1]==n:
            break
    return A

print(*solve())

### FIXED CODE ###

import sys
from itertools import accumulate
input=sys.stdin.buffer.readline

def main():
    n, k = map(int, input().split())
    A = [*map(int, input().split())]
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            if i>v:
            # b[max(0,i-v)]+=1
                b[i-v]+=1
            else:
                b[0]+=1
            j=i-~v
            # if i+v+1<n:
            #     b[i+v+1]-=1
            if j<n:
                b[j]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

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

a, b = map(int, input().split())
n = min(a, b)
def get_primenumber(N):
    #素数リスト
    prime_list = [2]
    #3からNまでの数字を一つずつ取り出す
    for num in range(3,N+1,2):
      #取り出した数字が素数リストの要素で割れなければ素数リストに追加する
      if all( num % prime != 0 for prime in prime_list):
        prime_list.append(num)

    return prime_list
l = get_primenumber(n)
count = 1
for p in l:
    if a % p == 0 and b % p == 0:
        count += 1
print(count)

### FIXED CODE ###

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

def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a
n = gcd(a, b)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

ans = set(prime_factorize(n))
print(len(ans)+1)
### BUGGY CODE ###

num = int(input())
nums = list(map(int,input().split()))
ans = 1
for j in nums:
    ans = ans * j
if(ans > pow(10,18)):
    print('-1')
else:
    print(ans)


### FIXED CODE ###

n = int(input())
a = [int(_) for _ in input().split()]
a.sort()
ans = 1
for i in a:
    if i == 0:
        ans = 0
        break
    ans *= i
    if ans > 10**18:
        ans = -1
        break
 
print(ans)
### BUGGY CODE ###

ma = lambda :map(int,input().split())
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
k = ni()
a = 0
for i in range(10**7):
    a=(a+7*pow(10,i,k))%k
    if a== 0:
        print(i+1)
        exit()


### FIXED CODE ###

ma = lambda :map(int,input().split())
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
k = ni()
a = 0
for i in range(10**6):
    a=(a+7*pow(10,i,k))%k
    if a== 0:
        print(i+1)
        break
else:
    print(-1)
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
MP=[list(input())for i in range(h)]
kyori=[[[] for i in range(w)]for i in range(h)]
def bfs(a,b):
    dist=[[0]*w for i in range(h)]
    dist[b][a]=0
    q=deque([(a,b)])
    while q:
        a,b=q.popleft()
        da=[1,0,-1,0]
        db=[0,1,0,-1]
        dd=dist[b][a]
        for i in range(4):
            na=a+da[i]
            nb=b+db[i]
            if 0<=na and na<=w-1 and 0<=nb and nb<=h-1:
                if dist[nb][na]==0 and MP[nb][na]=='.':
                    dist[nb][na]=dd+1
                    kyori[nb][na].append(dd+1)
                    q.append((na,nb))
for i in range(h):
    for j in range(w):
        if MP[i][j]=='#':
            bfs(j,i)
ans=0
for i in range(h):
    for j in range(w):
        if MP[i][j]=='.':
            if kyori[j][i] !=[]:
                ans=max(ans, min(kyori[j][i]))
print(ans)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
AA = [list(input()) for _ in range(h)]
# AA[h][w]
infi = 10 ** 5
kouho = []
ans = [[infi] * (w) for _ in range(h)]

for i in range(h):
    for j in range(w):
        if AA[i][j] == "#":
            kouho.append((i, j, 0))
            ans[i][j] = 0

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


que = deque(kouho)
while que:
    py, px, d = que.popleft()
    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if nx < 0 or nx >= w:
            continue
        if ny < 0 or ny >= h:
            continue
        if ans[ny][nx] == infi:
            ans[ny][nx] = d + 1
            que.append((ny, nx, d + 1))


cnt = 0
for i in range(h):
    for j in range(w):
        cnt = max(cnt, ans[i][j])

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

n = int(input())
nodes = []
id_list = []
output = [None for i in range(n)]
cnt = 0
root = set(range(n))
for i in range(n):
    id, _, *li = list(map(int, input().split(' ')))
    root -= set(li)
    nodes.append(li)
    id_list.append(id)

def rooted_tree(id, depth, parent):
    out = {}
    ind = id_list.index(id)
    out['node'] = id
    out['parent'] = parent
    out['depth'] = depth
    out['c'] = nodes[ind]
    if depth == 0:
        out['type'] = 'root'
    elif len(nodes[ind]) == 0:
        out['type'] = 'leaf'
    else:
        out['type'] = 'internal node'
    output[id] = out
    for i in (nodes[ind]):
        rooted_tree(i, depth+1, id)

rooted_tree(root.pop(), 0, -1)
for line in output:
    print("node {}: parent = {}, depth = {}, {}, {}".format(line['node'], line['parent'], line['depth'], line['type'], line['c']))



### FIXED CODE ###

n = int(input())
nodes = [0 for i in range(n)]
output = [None for i in range(n)]
cnt = 0
root = set(range(n))
for i in range(n):
    id, _, *li = list(map(int, input().split(' ')))
    root -= set(li)
    nodes[id] = li

def rooted_tree(id, depth, parent):
    out = {}
    out['node'] = id
    out['parent'] = parent
    out['depth'] = depth
    out['c'] = nodes[id]
    if depth == 0:
        out['type'] = 'root'
    elif len(nodes[id]) == 0:
        out['type'] = 'leaf'
    else:
        out['type'] = 'internal node'
    output[id] = out
    for i in (nodes[id]):
        rooted_tree(i, depth+1, id)

rooted_tree(root.pop(), 0, -1)
for line in output:
    print("node {}: parent = {}, depth = {}, {}, {}".format(line['node'], line['parent'], line['depth'], line['type'], line['c']))
### BUGGY CODE ###

#区間[L,R]に1を加えていく
def seg_tree_update(L,R):
    L,R=2**m-1+L,2**m-1+R
    while L<R:
        if L%2==0:
            tree[L]+=1
        if R%2==1:
            tree[R]+=1
        L//=2
        R=R//2-1
    if L==R:
        tree[L]+=1

#数直線xでの和を求める
def seg_tree_sumarize(x):
    ind=2**m-1+x
    SUM=tree[ind]
    ind=(ind-1)//2
    while ind>=0:
        SUM+=tree[ind]
        ind=(ind-1)//2
    return SUM

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

data=[]

for i in range(N):
    l,r=map(int,input().split())
    data.append([r-l, l, r])

data.sort()

m=0
while pow(2,m)<M+1:
    m+=1
tree=[0]*(pow(2,m+1)-1)

i=0
for d in range(1,M+1):
    
    #間隔の長さがd以下の区間だけ考えれば良い。
    while i<N and data[i][0]<d:
        seg_tree_update(data[i][1],data[i][2])
        i+=1
    
    ans=0
    
    for j in range((M+1)//d+1):
        if d*j>M:
            break
        ans+=seg_tree_sumarize(d*j)
    
    print(ans+N-i)

### FIXED CODE ###

"""
BIT
区間[L,R]にxを加える。
座標Xでの値を求める。
"""
import sys
input=sys.stdin.readline

def bit_add(i,x):
    while i<=M:
        tree[i]+=x
        i+=i&(-i)

def bit_sum(i):
    s=0
    while i>0:
        s+=tree[i]
        i-=i&(-i)
    return s

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

data=[]
for i in range(N):
    l,r=map(int,input().split())
    data.append([r-l, l, r])
data.sort()

k=0
tree=[0]*(M+1)
for d in range(1,M+1):
    
    #間隔の長さがd以下の区間だけ考えれば良い。
    while k<N and data[k][0]<d:
        bit_add(data[k][1],1)
        bit_add(data[k][2]+1,-1)
        k+=1
    
    ans=0
    for j in range(1,M//d+1):
        ans+=bit_sum(d*j)
    
    print(ans+N-k)
### BUGGY CODE ###

from numba import jit
@jit
def main():
  n=int(input())
  ans=0
  for c in range(1,n):
    k=int((n-c)**(1/2))
    for a in range(1,k+1):
      if (n-c)%a==0:
        if a**2==n-c:
          ans+=1
        else:
          ans=ans+2
  print(ans)
main()

### FIXED CODE ###

n=int(input())
ans=0
for a in range(1,n):
  ans+=(n-1)//a
print(ans)
### BUGGY CODE ###

import numpy as np

n = int(input())
x=[int(i)for i in input().split()]
x=[np.array([(X>>i)&1 for i in range(20)])for X in x]

bit = 0
j=0
ans = 0

for i in range(n):
    bit += x[i]    
    while True:
        flag=False
        for b in bit:
            if b > 1:
                flag=True
                break
        if flag==True:
            bit -= x[j]
            j+=1
            continue
        else:
            break
    ans += i-j+1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans=1
tmp = a[0]
l=0
for i in range(1,n):
    x = a[i]
    while tmp^x != tmp+x:
        tmp-=a[l]
        l+=1
    ans+=i-l+1
    tmp+=x
print(ans)
### BUGGY CODE ###

import numpy as np
h, n = map(int, input().split())
dp = np.zeros((n+1, h+1))
dp[0] = np.inf
for i in range(1, n+1):
    a, b = map(int, input().split())
    for j in range(1, h+1):
        if j >= a:
            dp[i][j] += min(
                dp[i-1][j], dp[i][j-a] + b,
            )
        else:
            dp[i][j] += min(
                dp[i-1][j], b
            )
print(int(dp[n][h]))


### FIXED CODE ###

h, n = map(int, input().split())
inf = 10**11

# dp[i]: 体力iを減らす魔力の最小値
dp = [inf] * 20000
dp[0] = 0

for _ in range(n):
    a, b = map(int, input().split())
    for j in range(h):
        dp[j+a] = min(dp[j] + b, dp[j+a])

print(min(dp[h:]))
### BUGGY CODE ###


def main():
    s = input()
    cnt = 0
    for i in range(len(s) - 4):
        for j in range(i + 4, len(s)):
            if int(s[i:j + 1]) % 2019 == 0:
                cnt += 1
    print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter


def main():
    MOD = 2019
    s = input()
    n = len(s)
    t = [0] * (n + 1)
    # n-1,n-2,...,0
    for i in range(n - 1, -1, -1):
        t[i] = t[i + 1] + pow(10, n - i - 1, MOD) * int(s[i])
        t[i] %= MOD
    c = Counter(t)
    cnt = 0
    for v in c.values():
        cnt += v * (v - 1) // 2
    print(cnt)


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

import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
r = set(list(range(n)))
N = n*(n-1) // 2 + 1
for _ in range(N):
    if not r:
        print(_)
        break
    ne = set()
    flag = True
    for j in r:
        if not a[j]:
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
            ne.add(j)
            ne.add(c-1)
    for j in list(ne):
        if a[j]:
            if a[j][0] == "-":
                a[j] = a[j][1:]
                flag = False
                if not a[j]:
                    ne.remove(j)
    if flag:
        print(-1)
        break
    else:
        r = ne


### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
r = set(list(range(n)))
N = n*(n-1) // 2 + 1
for _ in range(N):
    if not r:
        print(_)
        break
    ne = set()
    flag = True
    for j in r:
        if not a[j]:
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
            ne.add(j)
            ne.add(c-1)
    for j in list(ne):
        if a[j]:
            if a[j][0] == "-":
                a[j].pop(0)
                flag = False
                if not a[j]:
                    ne.remove(j)
    if flag:
        print(-1)
        break
    else:
        r = ne
### BUGGY CODE ###

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

cnt = 0
for i in range(a, b+1):
    if i % x == 0:
        cnt += 1
print(cnt)

### FIXED CODE ###

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

def calc(n):
    if n > -1 :
        cnt = n // x  + 1
    else:
        cnt = 0
    return int(cnt)
    
cnt_a = calc(a-1)
cnt_b = calc(b)

ans = cnt_b - cnt_a
print(int(ans))
### BUGGY CODE ###

# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H, W):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, W = read_ints()
A = read_map(H, W)


# print(A)

from itertools import product


# 開始地点
start = []
for i, a in enumerate(A):
    for j, aa in enumerate(a):
        if aa == '#':
            start.append((i, j))


def mahattan(sy, sx, ey, ex):
    return abs(sy - ey) + abs(sx - ex)


ans = 0
for i, j in product(range(H), range(W)):
    if A[i][j] == '.':
        tmp = 10000
        for ey, ex in start:
            tmp = min(tmp, mahattan(i, j, ey, ex))
        ans = max(ans, tmp)

print(ans)


### FIXED CODE ###

# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H, W):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, W = read_ints()
A = read_map(H, W)

from itertools import product
from collections import deque


# 開始地点
start = []
for i, a in enumerate(A):
    for j, aa in enumerate(a):
        if aa == '#':
            start.append((i, j))


# 探索の準備
mvx = (1, 0, -1, 0)
mvy = (0, 1, 0, -1)
visited = [[False for _ in range(W)] for _ in range(H)]

n_white = W*H
que = deque([(si, sj, 0) for si, sj in start])

for si, sj in start:
    visited[si][sj] = True

# 幅優先探索
while que:
    y, x, cost = que.popleft()
    # 白マスの数の管理
    n_white -= 1
    if n_white == 0:
        ans = cost
        break

    for dy, dx in zip(mvy, mvx):
        y_new, x_new = y + dy, x + dx
        # 探索に含めない条件
        if not (-1 < y_new < H) or not (-1 < x_new < W):
            continue
        if visited[y_new][x_new]:
            continue

        # 探索に追加してあげる
        que.append((y_new, x_new, cost + 1))
        visited[y_new][x_new] = True


print(cost)
### BUGGY CODE ###

#全探索すると終わらない
import math
N, M = map(int, input().split())
ans = 1
    
for i in range((M+N-1)//N, 0, -1):
    if M%i == 0:
        if (M//i)//N >= 1:
            print (i)
            exit()


### FIXED CODE ###

#全探索すると終わらない
import math
N, M = map(int, input().split())
ans = 1
    
for i in range((M+N-1)//N, 0, -1):
    if M%i == 0:
        if (M//i)//N >= 1:
            print (i)
            exit()
### BUGGY CODE ###

#!/usr/bin/env python3
import io
import os


def main():
    n, m = map(int, input().split())
    wi, vi = map(int, input().split())

    dp = [0] * (m + 1)
    for i in range(wi, m + 1):
        dp[i] = vi

    for i in range(n - 1):
        wi, vi = map(int, input().split())
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
main()


### FIXED CODE ###

#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

print(dp[-1][-1])
### BUGGY CODE ###

import heapq
n,m=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
d=[-1*i for i in a]
for i in range(m):
    heapq.heapify(d)
    b=heapq.heappop(d)
    b=b/2
    heapq.heappush(d,b)
c=[int(i) for i in d]

ans=0
for i in c:
    ans+=i
print(-1*ans)

### FIXED CODE ###

import heapq
n,m=[int(i) for i in input().split()]
a=[-1*int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    b=heapq.heappop(a)
    b=b/2
    heapq.heappush(a,b)
ans=0
for i in a:
    ans-=int(i)
print(ans)
### BUGGY CODE ###

K = int(input())

if K%2 == 0 or K%2 ==0:
    print(-1)
    exit(0)

count = 0
an = 0
while True:
  an = (10*an + 7) % K
  count +=1
  if an == 0:
    print(count)
    break

### FIXED CODE ###

def calc(k):
    cur = 0
    for i in range(1, 10 ** 7):
        cur *= 10
        cur += 7
        cur %= k
        if cur == 0:
            return i

    return -1


k = int(input())
print(calc(k))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
N=int(sys.stdin.readline().strip())
S=sys.stdin.readline().strip()
ans=0   #文字列一致が存在しない場合は0を返す

for i in range(N):
    s=S[i]
    for j in range(i+1,N):
        while j<N:  #jが文字列からはみ出さない間はループを回す
            t=S[j]
            if s==t:    #文字が一致したら、jを1つ進める
                current_j=j     #文字が一致したら現在のjの位置を記録しておく
                cnt=0
                while s==t:
                    cnt+=1
                    i+=1    #チェックする文字を1文字ずつ右にスライド
                    j+=1    #チェックする文字を1文字ずつ右にスライド
                    if i==current_j:    #iがjのスタート位置と重なったらbreak
                        break
                    elif i<N and j<N:    #i,jともに文字列内だったら
                        s=S[i]
                        t=S[j]
                    else:    #i or jが文字列の右側からはみ出したら
                        break
                ans=max(ans,cnt)
                j=current_j+1 #元のjの値を戻して、1つ進める
            else:    #文字が一致しなかったら、jを1つ進める
                j+=1

print ans

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict
N=input()
s=raw_input()

str="abcdefghijklmnopqrstuvwxyz"
D={}
for i,str in enumerate(str):
	D[str]=i+1

base=27
mod=2**61-1
hash=[]

for i,x in enumerate(s):
	if i==0: hash.append(D[x]%mod)
	else: hash.append( (hash[-1]*base+D[x])%mod )

def get(l,r):
	if l==0: return hash[r-1]%mod
	else: return ( hash[r-1]-hash[l-1]*pow(base,(r-l),mod) )%mod

# 長さmを固定し、区間 [i, i + m) のハッシュ値を求めて、長さmの共通文字列があるかを判定
def check(m):
	C={}
	for i in range(N):
		if i+m<=N:
			hash_value=get(i,i+m)
			if hash_value in C:
				if m<=i-C[hash_value]:
					return True
			else:
				C[hash_value]=i
	else:
		return False

l=0
h=N

while 1<(h-l):
	m=(l+h)/2
	if check(m):
		l=m
	else:
		h=m

print l
### BUGGY CODE ###

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

cost_list = list(map(int, input().split()))

max_num = 0
max_profit = 0

for i in range(len(cost_list)-1):
    profits = [x - cost_list[i] for x in cost_list[i+1 :]]
    M_profit = max(profits)

    if max_profit < M_profit:
        max_num = 1
        max_profit = M_profit

    elif max_profit == M_profit:
        max_num += 1

print(max_num)


### FIXED CODE ###

import numpy as np
N, T = map(int, input().split())

cost_list = np.array(list(map(int, input().split())))

max_num = 0
max_profit = 0
max_list = []
max_value = 0
for x in reversed(cost_list[1:]):
    max_value = max(max_value, x)
    max_list.append(max_value)
max_list = list(reversed(max_list))
max_list = np.array(max_list)
res = max_list - cost_list[:-1]

res_max = max(res)

max_num_list = [y for y in res if y == res_max]

print(len(max_num_list))
### BUGGY CODE ###

from collections import deque

def main():
    A,B,N=map(int,input().split())
    d=deque()
    
    for x in range(N+1):
        #tmp=((A*x)//B)-A*(x//B)
        if (A*x<B):
            tmp1=0
        if (x<B):
            tmp2=0
        tmp1=((A*x)//B)
        tmp2=A*(x//B)
        tmp=tmp1-tmp2
        
        if x>=1:
            if d[-1]>tmp:
                break
        
        d.append(tmp)
        
    print(d[-1])
    exit()
    
if __name__=="__main__":
    main()


### FIXED CODE ###

from math import floor

def main():
    A,B,N=map(int,input().split())
    
    ans1=min(N,B-1)
    ans2=floor(A*ans1/B)-A*floor(ans1/B)
    print(ans2)
    
if __name__=="__main__":
    main()