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

import heapq
import sys
input = sys.stdin.readline


def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    重み付きグラフgraphは隣接リストで与えられる
    計算量: O(|E|log|V|)
    """
    INF = float("inf")
    n = len(graph)
    distance = [INF] * n
    distance[start] = 0
    
    q = [(start, 0)]  #q = [(現在地, startからの距離)]
    while q:
        pos, dist = heapq.heappop(q)
        if distance[pos] < dist:
            continue
        distance[pos] = dist
        for next_pos, cost in graph[pos]:
            if distance[pos] + cost < distance[next_pos]:
                distance[next_pos] = distance[pos] + cost
                heapq.heappush(q, (next_pos, distance[next_pos]))
    return distance


n, m, s, t = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

y_graph = [[] for i in range(n)]
s_graph = [[] for i in range(n)]
for u, v, a, b in info:
    u -= 1
    v -= 1
    y_graph[u].append((v, a))
    y_graph[v].append((u, a))
    s_graph[u].append((v, b))
    s_graph[v].append((u, b))

s -= 1
t -= 1
y_cost = dijkstra(s, y_graph)
s_cost = dijkstra(t, s_graph)

ans = [0]*n
for i in range(n):
    ans[i] = y_cost[i] + s_cost[i]

for i in range(n-1)[::-1]:
    ans[i] = min(ans[i], ans[i+1])

for num in ans:
    print(10**15 - num)

### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline


def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    重み付きグラフgraphは隣接リストで与えられる
    計算量: O(|E|log|V|)
    """
    INF = float("inf")
    n = len(graph)
    distance = [INF] * n
    distance[start] = 0
    q = [(0, start)]  #q = [(startからの距離, 現在地)]
    while q:
        dist, pos = heapq.heappop(q)
        if distance[pos] < dist:
            continue
        for next_pos, cost in graph[pos]:
            if distance[pos] + cost < distance[next_pos]:
                distance[next_pos] = distance[pos] + cost
                heapq.heappush(q, (distance[next_pos], next_pos))
    return distance


n, m, s, t = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

y_graph = [[] for i in range(n)]
s_graph = [[] for i in range(n)]
for i in range(m):
    u, v, a, b = info[i]
    u -= 1
    v -= 1
    y_graph[u].append((v, a))
    y_graph[v].append((u, a))
    s_graph[u].append((v, b))
    s_graph[v].append((u, b))

s -= 1
t -= 1
y_cost = dijkstra(s, y_graph)
s_cost = dijkstra(t, s_graph)

ans = [0]*n
for i in range(n):
    ans[i] = y_cost[i] + s_cost[i]

for i in range(n-1)[::-1]:
    ans[i] = min(ans[i], ans[i+1])

for num in ans:
    print(10**15 - num)
### BUGGY CODE ###

import sys
from heapq import heappush,heappop
input=sys.stdin.readline
n,q=map(int,input().split())
e=[]
for i in range(n):
  s,t,x=map(int,input().split())
  e.append((s-x,1,x))
  e.append((t-x,-1,x))
for i in range(q):
  d=int(input())
  e.append((d,2,0))
e.sort()
s=set()
a=[]
for time_,type_,x_ in e:
  if type_==1:
    s.add(x_)
    heappush(a,x_)
  elif type_==-1:
    s.remove(x_)
  else:
    while a and a[0] not in s:
      heappop(a)
    if a:
      print(a[0])
    else:
      print(-1)

### FIXED CODE ###

import sys
from heapq import heappush,heappop
input=sys.stdin.readline
n,q=map(int,input().split())
e=[]
for i in range(n):
  s,t,x=map(int,input().split())
  e.append((s-x,1,x))
  e.append((t-x,-1,x))
for i in range(q):
  d=int(input())
  e.append((d,2,0))
e.sort()
s=set()
a=[]
for time_,type_,x_ in e:
  if type_==1:
    s.add(x_)
    heappush(a,x_)
  elif type_==-1:
    s.remove(x_)
  else:
    while a and a[0] not in s:
      heappop(a)
    if a:
      print(a[0])
    else:
      print(-1)
### BUGGY CODE ###

N = int(input())
S = [input() for _ in [0]*N]

A = [(0,0)]*N
B = [(0,0)]*N
for i,T in enumerate(S):
    m = 0
    M = 0
    tot = len(T) - T.count(")")*2
    if tot>=0:
        tot = 0
        for t in T:
            if t==")":
                tot -= 1
                m = min(m,tot)
            else:
                tot += 1
        A[i] = (m,tot)
    else:
        tot = 0
        for t in T[::-1]:
            if t==")":
                tot += 1
            else:
                tot -= 1
                m = min(m,tot)
        B[i] = (m,tot)

A.sort(reverse=True)
B.sort(reverse=True)

totA = 0
ans = True
for m,t in A:
    if totA + m < 0:
        ans = False
        break
    totA += t
totB = 0
for m,t in B:
    if totB + m < 0:
        ans = False
        break
    totB += t
if totA != totB:
    ans = False

if ans:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = int(input())
S = [input() for _ in [0]*N]

A = [(0,0)]*N
B = [(0,0)]*N
for i,T in enumerate(S):
    m = 0
    M = 0
    tot = len(T) - T.count(")")*2
    if tot>=0:
        tot = 0
        for t in T:
            if t==")":
                tot -= 1
                m = min(m,tot)
            else:
                tot += 1
        A[i] = (m,tot)
    else:
        tot = 0
        for t in T[::-1]:
            if t==")":
                tot += 1
            else:
                tot -= 1
                m = min(m,tot)
        B[i] = (m,tot)

A.sort(reverse=True)
B.sort(reverse=True)

totA = 0
ans = True
for m,t in A:
    if totA + m < 0:
        ans = False
        break
    totA += t
totB = 0
if ans:
    for m,t in B:
        if totB + m < 0:
            ans = False
            break
        totB += t
    if totA != totB:
        ans = False

if ans:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import sys
readline=sys.stdin.readline

H,W,M = map(int,readline().split())

hcol = [[0,i] for i in range(H)]
wcol = [[0,i] for i in range(W)]

P = set()
for i in range(M):
  h,w = map(int,readline().split())
  h -= 1
  w -= 1
  hcol[h][0] += 1
  wcol[w][0] += 1
  P.add((h,w))
  
hcol = sorted(hcol, key = lambda x:x[0], reverse = True)
wcol = sorted(wcol, key = lambda x:x[0], reverse = True)

hmax = hcol[0][0]
wmax = wcol[0][0]

ans = 0
hind = 0
wind = 0
while hind < H:
  while wind < W:
    val = hcol[hind][0] + wcol[wind][0]
    if (hcol[hind][1],wcol[wind][1]) in P:
      val -= 1
    if ans < val:
      ans = val
    wind += 1
    if wind == W or wcol[wind][0] < wmax:
      wind = 0
      break
  hind += 1
  if hind == H or hcol[hind][0] < hmax:
    break
    
print(ans)



### FIXED CODE ###

import sys
readline=sys.stdin.readline

H,W,M = map(int,readline().split())

hcol = [[0,i] for i in range(H)]
wcol = [[0,i] for i in range(W)]

P = set()
for i in range(M):
  h,w = map(int,readline().split())
  h -= 1
  w -= 1
  hcol[h][0] += 1
  wcol[w][0] += 1
  P.add((h,w))
  
hcol = sorted(hcol, key = lambda x:x[0], reverse = True)
wcol = sorted(wcol, key = lambda x:x[0], reverse = True)

hmax = hcol[0][0]
wmax = wcol[0][0]

ans = 0
hind = 0
wind = 0

# 交点がないものがあればhmax + wmaxが答え
found = False
while hind < H:
  while wind < W:
    val = hcol[hind][0] + wcol[wind][0]
    if (hcol[hind][1],wcol[wind][1]) in P:
      val -= 1
    else:
      found = True
      ans = val
      break
    if ans < val:
      ans = val
    wind += 1
    if wind == W or wcol[wind][0] < wmax:
      wind = 0
      break
  if found:
    break
  hind += 1
  if hind == H or hcol[hind][0] < hmax:
    break
    
print(ans)
### BUGGY CODE ###

N=int(input())
S=list(map(int,input().split()))
count=0
P=[0]*(N*N+1)
for j in range(N*N):
  P[j+1]=S.index(j+1)
d=[-1]*(N*N+1)
for i in range(N*N):
  player=S[i]
  hayasa=P[player]
  
  que=[[] for _ in range(N)]
  que[0].append(player)
  d[player]=i
  
  j=0
  finish=0
  while True:
    for kouho in que[j]:
      if kouho%N==0:
        finish=1
        break
      if kouho%N==1:
        finish=1
        break
      if kouho+N>N*N:
        finish=1
        break
      if kouho<N:
        finish=1
        break
        
      if d[kouho+N]<i:
        if P[kouho+N]>hayasa:
          que[j+1].append(kouho+N)
          d[kouho+N]=i
        else:
          que[j].append(kouho+N)
          d[kouho+N]=i
          
      if d[kouho-N]<i:
        if P[kouho-N]>hayasa:
          que[j+1].append(kouho-N)
          d[kouho-N]=i
        else:
          que[j].append(kouho-N)
          d[kouho-N]=i
          
      if d[kouho+1]<i:
        if P[kouho+1]>hayasa:
          que[j+1].append(kouho+1)
          d[kouho+1]=i
        else:
          que[j].append(kouho+1)
          d[kouho+1]=i
          
      if d[kouho-1]<i:
        if P[kouho-1]>hayasa:
          que[j+1].append(kouho-1)
          d[kouho-1]=i
        else:
          que[j].append(kouho-1)
          d[kouho-1]=i
    if finish==1:
      count+=j
      break
    j+=1    
print(count)

### FIXED CODE ###

from numba import njit
import numpy as np

@njit
def main(N, P):
    lista = [1, -1, N, -N]
    d = np.zeros((N, N), dtype=np.int32)
    d = d.ravel()
    sit = np.ones_like(d)
    stack = np.empty_like(d)
    count = 0
    for i in range(N*N):
        d[i] = min(i % N, (N-1-i) % N, i//N, N-1-i//N)
    for player in P:
        sit[player-1] = 0
        count += d[player-1]
        stack[0] = player
        num = 0
        while num >= 0:
            p = stack[num]
            num -= 1
            a = d[p-1]+sit[p-1]
            for i in lista:
                if p+i < 1 or p + i > N*N:
                    continue
                if d[p+i-1] > a:
                    d[p+i-1] = a
                    num += 1
                    stack[num] = p+i
    print(count)

N = int(input())
P = np.array(input().split(), np.int32)

main(N, P)
### BUGGY CODE ###

A, B, K = map(int, input().split())
for i in range(K):
    if A >= 1:
        A -= 1
    elif B >= 1:
        B -= 1
    else:
        continue
print(A, B)

### FIXED CODE ###

A, B, K = map(int, input().split())
if K <= A:
    print(A-K, B)
elif A < K <= A+B:
    print(0, B-(K-A))
else:
    print(0, 0)
### BUGGY CODE ###

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


dic = {}
ans = 0
prev = -1
for t in sorted(A):
    # if t in dic.keys():
    #     continue
    if prev == t:
        continue
    tmp = A.count(t)
    dic[t] = tmp
    ans += tmp * (tmp - 1) // 2
    prev = t

for i in range(N):
    val = dic.get(A[i])
    print(ans-val+1)

### FIXED CODE ###

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

dic = {}
ans = 0
# for t in A:
#     if t in dic.keys():
#         continue
#     tmp = A.count(t)
#     dic[t] = tmp
#     ans += tmp*(tmp-1)//2

for a in A:
    tmp = dic.get(a)
    if tmp == None:
        dic[a] = 1
    else:
        dic[a] = tmp + 1

for key in list(dic.keys()):
    tmp = dic.get(key)
    ans += tmp * (tmp - 1) // 2
    

for a in A:
    val = dic.get(a)
    print(ans-val+1)
### BUGGY CODE ###

N = int(input())
S = input()
ans = N
for i in range(N):
    x = S[:i].count('W') + S[i + 1:].count('E')
    if x < ans:
        ans = x
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = N
x = 0
y = S.count('E')
for i in range(N):
    if S[i-1] == 'W' and i > 0:
        x += 1
    if S[i] == 'E':
        y -= 1
    if x + y < ans:
        ans = x + y
print(ans)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for i in range(q):
  l,r=map(int,input().split())
  print(s[l-1:r].count('AC'))

### FIXED CODE ###

from itertools import accumulate
n, q = map(int, input().split())
s = input()
L = [0]*n
for i in range(1, n):
    if(s[i-1:i+1] == 'AC'):
        L[i] = 1
c = list(accumulate(L))
for i in range(q):
    l, r = map(int, input().split())
    print(c[r-1]-c[l-1])
### BUGGY CODE ###

import numpy as np
N,K,Q=map(int,input().split())
score=np.ones(N,dtype=int)*K
loss=np.ones(N,dtype=int)
for i in range(Q):
  A=int(input())
  score=score-loss
  score[A-1]+=1
for i in range(N):
  if(score[i]<=0):
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

N,K,Q=map(int,input().split())
count=[0 for i in range(N)]
for i in range(Q):
  A=int(input())
  count[A-1]+=1
for i in range(N):
  if(count[i]>Q-K):
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

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

seki_list = []
seki = 1
temp = 0

seki_list_append = seki_list.append

for i in A:
    seki *= i
    seki_list_append(seki)

point = seki_list[k-1]

for i in range(k, n):
    temp = seki_list[i]/seki_list[i-k]
    if temp > point:
        print("Yes")
        point = temp
    else:
        print("No")
        point = temp


### FIXED CODE ###

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

for i in range(k,n):
    if A[i] > A[i-k]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

def erastotenes(n):
    prime=[2]
    limit=int(n**0.5)
    data=[i+1 for i in range(2, n, 2)]      #奇数のリストを作成
    while True:
        p=data[0]
        if p>=limit:
            return prime+data
        prime.append(p)
        data=[e for e in data if e%p!=0]


naturals=erastotenes(100000)

q=int(input())
for _ in range(q):
    left, right=map(int,input().split())
    count=0
    for i in range(left, right+1):
        if i==1 or i%2==0:
            continue
        if i in naturals and int((i+1)/2) in naturals:
            count+=1
    print(count)

### FIXED CODE ###

def get_isPrime(n):         #1~nまでの数で、素数は1、それ以外は0となるようなリストを返す
    isprime=[1]*(n+1)
    isprime[0]=0
    isprime[1]=0
    for i in range(2, int(n**0.5)+1):
        if not isprime[i]:
            continue
        for j in range(i*2, n+1, i):
            isprime[j]=0
    return isprime

max_n=100000
isprime=get_isPrime(max_n)

ruiseki=[]
for i in range(max_n+1):
    if i==0 or i==1 or i==2:
        ruiseki.append(0)
    else:
        if i%2==0:
            ruiseki.append(ruiseki[i-1])
        else:
            if isprime[i] and isprime[int((i+1)/2)]:
                ruiseki.append(ruiseki[i-1]+1)
            else:
                ruiseki.append(ruiseki[i-1])

q=int(input())
for _ in range(q):
    left, right=map(int,input().split())
    print(ruiseki[right]-ruiseki[left-1])
### BUGGY CODE ###

s = input()
k = int(input())
a =[chr(ord('a') + i) for i in range(26)]

tar = set()
alpha_idx = 0
while len(tar) < k:
    alpha = a[alpha_idx]
    for i in range(len(s)):
        if s[i] == alpha:
            for j in range(i+1, len(s)+1):
                tar.add(s[i:j])
    alpha_idx += 1
tar = list(tar)
tar.sort()
print(tar[k-1])



### FIXED CODE ###

s = input()
k = int(input())
a =[chr(ord('a') + i) for i in range(26)]

tar = set()
alpha_idx = 0
while len(tar) < k:
    alpha = a[alpha_idx]
    for i in range(len(s)):
        if s[i] == alpha:
            for j in range(i+1, min(len(s)+1,i+1+k)):
                tar.add(s[i:j])
    alpha_idx += 1
tar = list(tar)
tar.sort()
print(tar[k-1])
### BUGGY CODE ###

N, Y = map(int, input().split(" "))

s1, s2, s3 = 10, 5, 1
ok_flg = False

if Y % 1000 != 0 :
    print("-1 -1 -1")    
else :
    y_small = int(Y / 1000)
    for i in range(N + 1) :
        if y_small - i * s1 <= (N - i) * s2 :
            for j in range(N - i + 1) :
                if y_small - i*s1 - j*s2 <= (N - i - j)*s3 :
                    for k in range(N - i - j + 1) :
                        # print("DBG : ", i, j, k, s1, s2, s3)
                        if i + j + k == N and i*s1 + j*s2 + k*s3 == y_small :
                            print(i, j, k)
                            ok_flg = True
                            break
                    if ok_flg == True :
                        break
            if ok_flg == True :
                break

    if ok_flg == False :
        print("-1 -1 -1")

### FIXED CODE ###

N, Y = map(int, input().split(" "))

s1, s2, s3 = 10, 5, 1
ok_flg = False

if Y % 1000 != 0 :
    print("-1 -1 -1")    
else :
    y_small = int(Y / 1000)
    for i in range(N + 1) :
        if y_small - i * s1 <= (N - i) * s2 :
            for j in range(N - i + 1) :
                if i + j <= N and i*s1 + j*s2 + (N - i - j)*s3 == y_small :
                    print(i, j, N - i - j)
                    ok_flg = True
                    break
                if ok_flg == True :
                    break
            if ok_flg == True :
                break
    if ok_flg == False :
        print("-1 -1 -1")
### BUGGY CODE ###

from sys import stdin,stdout
n,k=map(int,stdin.readline().split())
h=[int(l) for l in stdin.readline().split()]
dp=[0,abs(h[0]-h[1])]
for i in range(2,n):
    ans=10**15
    num=i-k
    if num<0:
        num=-1
    else:
        num-=1
    for j in range(i-1,num,-1):
        ans=min(abs(h[i]-h[j])+dp[j],ans)
    dp.append(ans)
print(dp[n-1])


### FIXED CODE ###

from sys import stdin,stdout
n,k=map(int,stdin.readline().split())
h=[int(l) for l in stdin.readline().split()]
dp=[0,abs(h[0]-h[1])]
for i in range(2,n):
    ans=10**15
    num=i-k
    if num<0:
        num=-1
    else:
        num-=1
    for j in range(i-1,num,-1):
        ans=min(abs(h[i]-h[j])+dp[j],ans)
    dp.append(ans)
print(dp[n-1])
### BUGGY CODE ###

import sys

def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    len1 = len(s1)
    len2 = len(s2)
    if len1 == 0 or len2 == 0:
        return 0

    primary = [0] * len1
    secondary = [0] * len1

    for i in range(len2):
        for j in range(len1):
            if s1[j] == s2[i]:
                match = 1
            else:
                match = 0
            if j == 0:
                secondary[j] = max(primary[j], match)
            else:
                sc1, p1, p2 = secondary[j-1], primary[j-1] + match, primary[j]
                if sc1 > p1:
                    if p1 > p2:
                        secondary[j] = sc1
                    elif p2 > sc1:
                        secondary[j] = p2
                    else:
                        secondary[j] = sc1
                else:
                    if sc1 > p2:
                        secondary[j] = p1
                    elif p1 > p2:
                        secondary[j] = p1
                    else:
                        secondary[j] = p2
                # secondary[j] = max(secondary[j-1], primary[j],
                #                    primary[j-1] + match)

        primary, secondary = secondary, primary

    return primary[len1-1]


def run():
    input()
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, len(s), 2):
        print(len_lcs(s[i], s[i+1]))


if __name__ == '__main__':
    run()



### FIXED CODE ###

import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            pr2 = results[j]
            if c1 == c2:
                mval = pr1 + 1
            elif sec1 > pr2:
                mval = sec1
            else:
                mval = pr2

            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]


def run():
    n = int(input())
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, 2*n, 2):
        print(len_lcs(s[i], s[i+1]))

run()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n,q=map(int,input().split())
s=input()
lr=[input() for i in range(q)]

ans=[]

for i in range(q):
    l,r=map(int,lr[i].split())
    #print(int((len(s[l-1:r])-len(s[l-1:r].replace('AC',"")))/2))
    ans.append(str(int((len(s[l-1:r])-len(s[l-1:r].replace('AC',"")))/2)))

print('\n'.join(ans))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
lr=[input() for __ in range(q)]
cs=[0]*(n+1)

#端がACで-1で止まる文字列指定は大丈夫？.
for i in range(n):
    cs[i+1]=cs[i] + (1 if s[i:i+2] == 'AC' else 0)

for num in lr:
    l,r=map(int,num.split())
    print(cs[r-1] - cs[l-1])
### BUGGY CODE ###

from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range(0, N):
    if i == 0:
        tmp = A[1]
    else:
        tmp = A[0]
    for j in range(0, N):
        if i != j:
            tmp = gcd(A[j], tmp)
        if tmp == 1:
            break
    ans = max(ans, tmp)
print(ans)


### FIXED CODE ###

from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
L = [0]
for i in range(1, N):
    L.append(gcd(A[i-1], L[i-1]))
R = [0]
for i in range(1, N):
    R.append(gcd(R[i-1], A[N-i]))
R.reverse()
ans = []
for i in range(0, N):
    ans.append(gcd(L[i], R[i]))
print(max(ans))
### BUGGY CODE ###

s = list(map(int, input().strip()))
len_s = len(s)

p = 0
count = 0

while p < len(s) - 1:
    if s[p] != s[p + 1]:
        count += 2
        first = s[:p] if p > 0 else []
        second = s[p + 2:] if p < len(s) - 2 else []
        s = first + second
        if p > 0:
            p -= 1
        else:
            p = 0
    else:
        p += 1

print(count)


### FIXED CODE ###

import numpy as np

s = list(map(int, input().strip()))
s = np.array(s, dtype=np.bool)
len_s = len(s)

p = 0
count = 0

while p < len_s - 1:
    if s[p] != s[p + 1]:
        count += 2
        if p < len_s - 2:
            s[p:-2] = s[p + 2:]
        if p > 0:
            p -= 1
        else:
            p = 0

        len_s -= 2
    else:
        p += 1

print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left

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

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

s = [i for i in range(1, M + 1)]
ret = 0
for a, b in AB :
    if a > s[-1] :
        continue
    
    a = bisect_left(s, a)
    s = s[:a] + s[a+1:]
    ret += b
    if not s :
        break
print(ret)


### FIXED CODE ###

from heapq import heappush, heappop

N, M = map(int, input().split())
AB = [[] for _ in range(M+1)]

for _ in range(N) :
    a, b = map(int, input().split())
    if a <= M :
        AB[M-a].append(b)
    
q = []
for a in range(M+1) :
    for b in AB[a] :
        heappush(q, b)
        if len(q) > a + 1 :
            heappop(q)
            
print(sum(q))