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

from collections import deque

h, w = map(int, input().split())
painted = [list(input()) for _ in range(h)]
starts = []
for y in range(h):
    for x in range(w):
        if painted[y][x] == '#':
            starts.append((y, x))


def paint_black(starts):
    que = deque()
    for start in starts:
        que.append(start)
    cnt = 0
    while not all([i == '#' for row in painted for i in row]):
        next_position = []
        cnt += 1
        while que:
            y, x = que.popleft()
            for iy, ix in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                ny = y + iy
                nx = x + ix
                if (0 <= ny < h) and (0 <= nx < w):
                    if painted[ny][nx] != '#':
                        painted[ny][nx] = '#'
                        next_position.append((ny, nx))

        for start in next_position:
            que.append(start)
    return cnt

cnt = paint_black(starts)
print(cnt)

### FIXED CODE ###

import sys

input = sys.stdin.readline


def main():
    h, w = map(int, input().split())
    # 蛮兵
    painted = [['#'] * (w + 2)]
    painted += [['#'] + list(input().rstrip()) + ['#'] for _ in range(h)]
    painted.append(['#'] * (w + 2))
    que = []

    for y in range(1, h + 1):
        for x in range(1, w + 1):
            if painted[y][x] == '#':
                painted[y][x] = 0
                que.append((y, x))
    while que:
        qq = []
        for y, x in que:
            if painted[y - 1][x] == '.':
                painted[y - 1][x] = painted[y][x] + 1
                qq.append((y - 1, x))
            if painted[y + 1][x] == '.':
                painted[y + 1][x] = painted[y][x] + 1
                qq.append((y + 1, x))
            if painted[y][x + 1] == '.':
                painted[y][x + 1] = painted[y][x] + 1
                qq.append((y, x + 1))
            if painted[y][x - 1] == '.':
                painted[y][x - 1] = painted[y][x] + 1
                qq.append((y, x - 1))
        que = qq

    print(painted[y][x])


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

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 
MOD = 10**9+7

S = inpS()
N = len(S)
dp = [[0]*13 for _ in range(N+1)]

dp[0][0] = 1
for dgt in range(N):
  for mo in range(13):
    if S[dgt] == "?":
      for nxt in range(10):
        ind = (mo*10 + nxt) % 13
        dp[dgt+1][ind] += dp[dgt][mo]
        dp[dgt+1][ind] %= MOD
    else:
      ind = (mo*10 + int(S[dgt])) % 13
      dp[dgt+1][ind] += dp[dgt][mo]
      dp[dgt+1][ind] %= MOD
print(dp[N][5])        

### FIXED CODE ###

import numpy as np
MOD = 10 ** 9 + 7

S = [int(x) if x != "?" else -1 for x in input()]
N = len(S)

# 現在考えてる一つ前の桁数で、余りが i になる整数の個数
r = [0]*13

# まず一つ目の値が１の位とする
s = S[0]
if s != -1:
  r[s] = 1
else:
  for i in range(10):
    r[i] = 1

# 桁を進めながら個数をカウント
for i in range(1, N):
    # dp[j]
    # 現在考えている桁(i)を除く、余りが j となる整数の個数
    dp = [0]*26
    # 桁が一つ上がるので、一つ前の余りが 10 倍になる
    for j in range(13):
      dp[j*10%13] += r[j] % MOD
    # アクセスを高速にするため２倍の長さとる (dp[i] == dp[i + 13])
    dp[13:26] = dp[0:13]
    r = [0]*13
    s = S[i]
    if s == -1:
      w = sum(dp[4:14])
      for j in range(13):
        r[j] += w
        w += dp[j+1] -dp[j+4]
    else:
      for j in range(13):
        r[j] += dp[13-s+j]
print(r[5]%MOD)
### BUGGY CODE ###

import sys

args = sys.argv

print(args)

def f(arg_list):
    even_arg_list = []
    for i in arg_list:
        if i % 2 == 0:
            even_arg_list.append(i/2)
        else:
            return False
    return even_arg_list


counter = 0
_list = map(lambda x:int(x),args[1:])
while True:
    _list = f(_list)
    if _list == False:
        print(counter)
        sys.exit()
    counter+=1
    print(_list)
    

### FIXED CODE ###

import sys

N = int(input())
Ai = map(lambda x:int(x),input().split(" "))
 
def f(arg_list):
    even_arg_list = []
    for i in arg_list:
        if i % 2 == 0:
            even_arg_list.append(i/2)
        else:
            return False
    return even_arg_list


counter = 0
while True:
    Ai = f(Ai)
    if Ai == False:
        print(counter)
        sys.exit()
    counter+=1
    # print(Ai)
### BUGGY CODE ###

n=int(input())
s=input()

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

ng=0

all=r*g*b

#NGパターン数の洗い出し
for i in range(0,n-2):
  for j in range(i,n-1):
    for k in range(j,n):
#      print(i,j,k)
      if j-i==k-j:
        if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
          ng+=1
print(all-ng)

### FIXED CODE ###

n=int(input())
s=input()

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

r,g,b=0,0,0

for i in range(0,n):
  if s[i]=='R':
    r+=1
  elif s[i]=='G':
    g+=1
  else:
    b+=1

ng=0

all=r*g*b

#NGパターン数の洗い出し
for i in range(0,n-2):
  for j in range(i,n-1):
    if s[i]==s[j]:
      continue
    else:
      if j*2-i<=n-1:
#        print(i,j,j*2-i)
        if s[j]!=s[j*2-i] and s[j*2-i]!=s[i]:
          ng+=1
print(all-ng)
### BUGGY CODE ###

# D
a, b, q = map(int, input().split())
s = [int(input()) for i in range(a)]
t = [int(input()) for i in range(b)]
x = [int(input()) for i in range(q)]

def route(start, mid, end):
    return abs(start-mid) + abs(mid-end)

for i in range(q):
    ans = 10000000000000000000000000
    # jinja
    j_list = [jin-x[i] for jin in s]
    if len([y for y in j_list if y<=0]) != 0:
        j_w = max([y for y in j_list if y<=0]) + x[i]
        t_list = [ter-j_w for ter in t]
        if len([y for y in t_list if y<=0]) != 0:
            t_w = max([y for y in t_list if y<=0]) + j_w
            ans = min(route(x[i], j_w,t_w), ans)
        else:
            t_e = min([y for y in t_list if y>0]) + j_w
            ans = min(route(x[i], j_w,t_e), ans)
    if len([y for y in j_list if y>0]) != 0:
        j_e = min([y for y in j_list if y>0]) + x[i]
        t_list = [ter-j_e for ter in t]
        if len([y for y in t_list if y<=0]) != 0:
            t_w = max([y for y in t_list if y<=0]) + j_e
            ans = min(route(x[i], j_e,t_w), ans)
        else:
            t_e = min([y for y in t_list if y>0]) + j_e
            ans = min(route(x[i], j_e,t_e), ans)
    t_list = [ter-x[i] for ter in t]
    if len([y for y in t_list if y<=0]) != 0:
        t_w = max([y for y in t_list if y<=0]) + x[i]
        j_list = [jin-t_w for jin in s]
        if len([y for y in j_list if y<=0]) != 0:
            j_w = max([y for y in j_list if y<=0]) + t_w
            ans = min(route(x[i], t_w,j_w), ans)
        else:
            j_e = min([y for y in j_list if y>0]) + t_w
            ans = min(route(x[i], t_w,j_e), ans)
    if len([y for y in t_list if y>0]) != 0:
        t_e = min([y for y in t_list if y>0]) + x[i]
        j_list = [jin-t_e for jin in s]
        if len([y for y in j_list if y<=0]) != 0:
            j_w = max([y for y in j_list if y<=0]) + t_e
            ans = min(route(x[i], t_e,j_w), ans)
        else:
            j_e = min([y for y in j_list if y>0]) + t_e
            ans = min(route(x[i], t_e,j_e), ans)
    print(ans)

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)
### BUGGY CODE ###


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]    

N, M, K = map(int,input().split())
uf = UnionFind(N)
frend = [set() for _ in range(N)]
block = [set() for _ in range(N)]
ans = []
for i in range(M):
    A, B = map(int,input().split())
    A -= 1
    B -= 1
    uf.union(A, B)
    frend[A].add(B)
    frend[B].add(A)
    
for i in range(K):
    C, D = map(int,input().split())
    C -= 1
    D -= 1
    block[C].add(D)
    block[D].add(C)    

for i in range(N):
    temp = uf.size(i) - 1
    for j in uf.members(i):
        if (j in frend[i]) or (j in block[i]):
            temp -= 1
    ans.append(temp)
print(*ans)

### FIXED CODE ###


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]
    
    def same(self, x, y):
        return self.find(x) == self.find(y)    
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]    

N, M, K = map(int,input().split())
uf = UnionFind(N)
f_b = [set() for _ in range(N)]
ans = []
for i in range(M):
    A, B = map(int,input().split())
    A -= 1
    B -= 1
    uf.union(A, B)
    uf.find(A)
    f_b[A].add(B)
    f_b[B].add(A)
    
for i in range(K):
    C, D = map(int,input().split())
    C -= 1
    D -= 1
    if uf.same(C, D):
        f_b[C].add(D)
        f_b[D].add(C)    

for i in range(N):
    ans.append(uf.size(i) - len(f_b[i]) - 1)
print(*ans)
### BUGGY CODE ###

from collections import deque
s=deque(list(input()))
q=int(input())
direction=0 #0:順 1:逆

for i in range(q):
    query=list(input().split())
    if query[0]=='1':
        direction=direction^1
    elif query[0]=='2':
        if query[1]=='1' and direction==0:
            s.appendleft(query[2])
        elif query[1]=='1' and direction==1:
            s.append(query[2])
        elif query[1]=='2' and direction==0:
            s.append(query[2])
        elif query[1]=='2' and direction==1:
            s.appendleft(query[2])

if direction==0:
    print(*s,sep='')
else:
    x=[]
    for i in range(len(s)):
        x.append(s[-1-i])
    print(*x,sep='')


### FIXED CODE ###

from collections import deque
s=deque(list(input()))
q=int(input())
direction=0 #0:順 1:逆

for i in range(q):
    query=input()
    if query[0]=='1':
        direction=direction^1
    elif query[0]=='2':
        i,f,c=query.split()
        if f=='1' and direction==0:
            s.appendleft(c)
        elif f=='1' and direction==1:
            s.append(c)
        elif f=='2' and direction==0:
            s.append(c)
        elif f=='2' and direction==1:
            s.appendleft(c)


if direction==0:
    print(''.join(s))
else:
    x=[]
    for i in range(len(s)):
        x.append(s[-1-i])
    print(''.join(x))
### BUGGY CODE ###

import pprint

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

day = 0

while True:
    end = 1
    game = list()
    for i in range(n):
        if a[i] != []:
            end = 0
            if a[a[i][0]-1] != []:
                if a[a[i][0]-1][0]-1 == i:
                    game.append(i)
    if end == 0:
        if game == []:
            print(-1)
            exit()
        else:
            for i in game:
                a[i].pop(0)
    else:
        print(day)
        exit()
    day += 1

### FIXED CODE ###

import pprint

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

day = 0
check = set(range(n))

while True:
    end = 1
    game = set()
    for i in check:
        if a[i] != []:
            end = 0
            if a[a[i][0]-1] != []:
                if a[a[i][0]-1][0]-1 == i:
                    game.add(i)
                    game.add(a[i][0]-1)
    if end == 0:
        if game == set():
            print(-1)
            exit()
        else:
            for i in game:
                a[i].pop(0)
    else:
        print(day)
        exit()
    day += 1
    check = game
### BUGGY CODE ###

from functools import reduce

mod = 998244353

def nCr(N,a):
    if a == 0:
        return 1
    num = reduce(lambda x,y:x * y % mod,range(N,N-a,-1))
    den = reduce(lambda x,y:x * y % mod,range(1,a+1))
    return num * pow(den,mod-2,mod)%mod

n,m,k = map(int,input().split())
ans = 0
nu = [1]
for i in range(n-1):
    nu.append((nu[-1]*(m-1))%mod)
for i in range(k+1):
    ans += (nu[-(i+1)]*nCr(n-1,i))% mod
print((m * ans)%mod)

### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353
N,m,k = map(int,input().split())
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ans = 0
for i in range(k+1):
    ans += (pow(m-1,N-1-i,mod)*cmb(N-1,i,mod))% mod
    ans %= mod
print((m * ans)%mod)
### BUGGY CODE ###

#import matplotlib.pyplot as plt

def main():
    a,b,n = map(int,input().split())
    mx = 0
    for x in range(min(b,n)//2,min(b+1,n+1)):
        left = int(a*x/b)
        right = a * int(x/b)
        #print("x=",x,"floor(Ax/B)=",int(a*x//b),"A*floor(x/B)=",a * int(x // b),"answer=",left-right)
        #right.append(a * int(x/b))

        mx = max(left-right,mx)
    print(mx)


    #plt.plot(list(range(len(right))),right,label="test")


if __name__ == '__main__':
    main()


### FIXED CODE ###

#import matplotlib.pyplot as plt

def main():
    a,b,n = map(int,input().split())
    x = min(b-1,n)



    print(int(a*x/b) - a * int(x/b))


    #plt.plot(list(range(len(right))),right,label="test")


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

N, M =  map(int,input().split(" "))
A = list(map(int,input().split(" ")))
A.sort()
BC = []
for i in range(M):
    B,C = map(int,input().split(" "))
    BC.append((B,C))

BC.sort(reverse=True,key=lambda x: x[1])

i = 0
for B,C in BC:
    for j in range(B):
        if C > A[i]:
            A[i] = C
            i += 1
        
        if i == N:
            break
    if i == N:
        break

print(sum(A))
        
    



### FIXED CODE ###

N, M =  map(int,input().split(" "))
A = list(map(int,input().split(" ")))
A.sort()
BC = []
for i in range(M):
    B,C = map(int,input().split(" "))
    BC.append((B,C))

BC.sort(reverse=True,key=lambda x: x[1])

i = 0
flg = True
for B,C in BC:
    for j in range(B):
        if C > A[i]:
            A[i] = C
            i += 1
        else:
            flg = False
            break

        if i == N:
            break
    if i == N or (not flg):
        break

print(sum(A))
### BUGGY CODE ###

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

dp = [0 for j in range(W + 1)]
for i in range(N):
  w, v = map(int, input().split())
  for wk in range(W, w - 1, -1):
    tv = dp[wk - w] + v
    if tv > dp[wk]:
      dp[wk] = tv

print(max(dp))


### FIXED CODE ###

def nap(n, cap):
    val = [0] * (cap + 1)
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap, w - 1, -1):
            nv = val[wk - w] + v
            if val[wk] < nv:
                val[wk] = nv
    return max(val)


n, cap = map(int, input().split())
print(nap(n, cap))
### BUGGY CODE ###

import sys, os
import collections

MOD = 10 ** 9 + 7

def solve(input_stream):
  N, K  = read_ints(input_stream)
  numbers = [i - 1 for i in map(int, input_stream.readline().strip().split())]
  cumulative_sum = [0 for i in range(N + 1)]
  mods = [0 for i in range(K)]
  ans = 0
  for index, number in enumerate(numbers):
    cumulative_sum[index + 1] = (cumulative_sum[index] + number) % K
  queue = []
  
  for index in range(N+1):
    ans += mods[cumulative_sum[index]]
    mods[cumulative_sum[index]] += 1
    queue.append(cumulative_sum[index])
    if len(queue) == K:
      target = queue.pop(0)
      mods[target] -= 1
  return [str(ans)]

  


def read_ints(input_stream):
  return [i for i in map(int, input_stream.readline().strip().split())]

def read_int(input_stream):
  return int(input_stream.readline().strip())


if __name__ == "__main__":
    outputs = solve(sys.stdin)
    for line in outputs:
      print(line)

### FIXED CODE ###

import sys, os
import collections

MOD = 10 ** 9 + 7

def solve(input_stream):
  N, K  = read_ints(input_stream)
  numbers = [int(i) - 1 for i in input_stream.readline().strip().split()]
  cumulative_sum = [0 for i in range(N + 1)]
  mods = {}
  ans = 0
  for index, number in enumerate(numbers):
    cumulative_sum[index + 1] = (cumulative_sum[index] + number) % K
  queue = []
  
  for index in range(N+1):
    if cumulative_sum[index] not in mods:
      mods[cumulative_sum[index]] = 0
    ans += mods[cumulative_sum[index]]
    mods[cumulative_sum[index]] += 1
    queue.append(cumulative_sum[index])
    if len(queue) == K:
      target = queue.pop(0)
      mods[target] -= 1
  return [str(ans)]

  


def read_ints(input_stream):
  return [i for i in map(int, input_stream.readline().strip().split())]

def read_int(input_stream):
  return int(input_stream.readline().strip())


if __name__ == "__main__":
    outputs = solve(sys.stdin)
    for line in outputs:
      print(line)
### BUGGY CODE ###


"""

https://atcoder.jp/contests/arc100/tasks/arc100_c

情報を再利用するのがメイン
K=Xの時は,K=X-1の時の答えに加え、 i or j == K の場合を考えればいい
or がKとなる場合、0の桁は両方0で、1の桁は片方が1ならよい
1では3通りの分け方があるので、3^N…

大きいほうから考えてみる？
最後は、当然最大のやつ2個→その2つのindex のORまではそれが保持

dp[X] = X と orしてもXのままのindexの集合における最大 & 2番目
→とすれば、1の桁全てに関して0にしてみた奴とXを見れば推移できる

O(2^N * logMAX(A)) で解けそうだ

"""

from sys import stdin

N = int(stdin.readline())
A = list(map(int,stdin.readline().split()))
A.append(float("-inf"))

dp = []
ans = 0

for i in range(2**N):

    if i == 0:
        dp.append( ( 0,-1 ) )
        continue

    dic = {}
    lis = [(A[i],i)]
    
    for j in range(N):

        if (2**j) & i > 0:

            ta,tb = dp[i ^ (2**j)]
            if ta not in dic:
                dic[ta] = 1
                lis.append( (A[ta],ta) )
            if tb not in dic:
                dic[tb] = 1
                lis.append( (A[tb],tb) )

    lis.sort()
    lis.reverse()

    aa,ab = lis[0][1] , lis[1][1]
    ans = max(A[aa] + A[ab] , ans)
    print (ans)
    dp.append( ( aa,ab ) )


### FIXED CODE ###


"""

https://atcoder.jp/contests/arc100/tasks/arc100_c

情報を再利用するのがメイン
K=Xの時は,K=X-1の時の答えに加え、 i or j == K の場合を考えればいい
or がKとなる場合、0の桁は両方0で、1の桁は片方が1ならよい
1では3通りの分け方があるので、3^N…

大きいほうから考えてみる？
最後は、当然最大のやつ2個→その2つのindex のORまではそれが保持

dp[X] = X と orしてもXのままのindexの集合における最大 & 2番目
→とすれば、1の桁全てに関して0にしてみた奴とXを見れば推移できる

O(2^N * logMAX(A)) で解けそうだ

"""

from sys import stdin

N = int(stdin.readline())
A = list(map(int,stdin.readline().split()))
A.append(float("-inf"))

dp = []
ans = 0
aaa = []

for i in range(2**N):

    if i == 0:
        dp.append( ( 0,-1 ) )
        continue

    na,nb = i,-1
    
    for j in range(N):

        if (2**j) & i > 0:

            ta,tb = dp[i ^ (2**j)]
            if A[na] < A[ta]:
                nb = na
                na = ta
            elif A[nb] < A[ta] and ta != na:
                nb = ta

            if A[nb] < A[tb]:
                nb = tb

    #print (i,na,nb)
    ans = max(A[na] + A[nb] , ans)
    aaa.append(ans)
    dp.append( ( na,nb ) )

print ("\n".join(map(str,aaa)))
### BUGGY CODE ###

def is_needed(i):
    dp = [False] * k
    dp[0] = True
    lm = 0
    for j, w in enumerate(aa):
        if i == j:
            continue
        set_lm = False
        for l in range(min(k - w - 1, lm), -1, -1):
            if dp[l]:
                dp[l + w] = True
                if not set_lm:
                    lm = l + w
                    set_lm = True
    return any(dp[k - aa[i]:])


n, k = map(int, input().split())
aa = sorted(map(int, input().split()))

l, h = 0, n - 1
while l <= h:
    c = (l + h) // 2
    if is_needed(c):
        h = c - 1
    else:
        l = c + 1
print(l)


### FIXED CODE ###

import bisect


def solve(k, aaa):
    aaa = aaa[:bisect.bisect_left(aaa, k)]

    dp = [False] * k
    dp[0] = True
    curr_max = 0
    ans = len(aaa)
    for i, a in reversed(list(enumerate(aaa))):
        if curr_max + a >= k:
            ans = i
        f = True
        for j in range(min(curr_max, k - a - 1), -1, -1):
            if dp[j]:
                dp[j + a] = True
                if f:
                    curr_max = max(curr_max, j + a)
                    f = False
    return ans


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

print(solve(k, aaa))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split(' ')]
if a[0] == 0:
    print(0)
else:
    x = 1
    for i in a:
        x = x * i
    if x > 10**18:
        print(-1)
    else:
        print(x)


### FIXED CODE ###

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

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

BA = []
for i in range(N):
  a, b = map(int, input().split())
  BA.append([b, a])

BA.sort(reverse=True)

ans = 0
used = [False] * (M+1)
for b, a in BA:
  if a >= M+1:
    continue
    
  while used[a]:
    a += 1
    if a == M+1:
      break
  
  if a <= M:
    used[a] = True
    ans += b

print(ans)

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
AB.sort()

ans = 0
candidates = []
now = 0
for i in range(M+1):
  for j in range(now, N):
    if AB[j][0] <= i:
      heapq.heappush(candidates, -AB[j][1])
      now = j + 1
      
    else:
      now = j
      break
  
  if candidates:
    ans -= heapq.heappop(candidates)

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

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

s = input()
K = int(input())

os = sorted(list(set(s).union()))

nth = 0
found = []
for o in os:
  samehead = []
  for i in range(len(s)):
    if s[i] == o:
      for j in range(i+1, len(s)+1):
        if s[i:j] in samehead: continue
        samehead.append(s[i:j])
  cands = sorted(samehead)
  if nth + len(cands) < K:
    found += samehead
    nth += len(cands)
    continue
  print(cands[K-nth-1])
  break


### FIXED CODE ###

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

s = input()
K = int(input())

os = sorted(list(set(s).union()))

nth = 0
found = []
for o in os:
  samehead = []
  for i in range(len(s)):
    if s[i] == o:
      for j in range(i+1, len(s)+1):
        if j-i>K: break
        if s[i:j] in samehead: continue
        samehead.append(s[i:j])
  cands = sorted(samehead)
  if nth + len(cands) < K:
    found += samehead
    nth += len(cands)
    continue
  print(cands[K-nth-1])
  break
### BUGGY CODE ###

N, M = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
li = [i for i in range(1, N+1)]
ans = li
for lr in LR:
  ans = [i for i in ans if lr[0] <= i <= lr[1]]
print(len(ans))

### FIXED CODE ###

N, M = map(int, input().split())
minNum = 1
maxNum = N
for lr in range(M):
  l, r = map(int, input().split())
  if minNum <= l and r <= maxNum:
    minNum = l
    maxNum = r
  elif minNum <= l <= maxNum and maxNum <= r:
    minNum = l
  elif l <= minNum and minNum <= r <= maxNum:
    maxNum = r
  elif r < minNum or maxNum < l:
    print("0")
    exit()
#  print(l,r,minNum,maxNum)
print(maxNum - minNum +1)