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

import sys
sys.setrecursionlimit(10 ** 8)
INF = 10 ** 15

class edge:
    def __init__(self, fr, to, cost):
        self.fr, self.to, self.cost = fr, to, cost

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, M = ZZ()
    es = []
    for _ in range(M):
        a, b, c = ZZ()
        a -= 1
        b -= 1
        es.append(edge(a, b, -c))

    #負の閉路検出
    d = [0] * N
    for i in range(N):
        for e in es:
            if d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
                if e.to == N-1 and i == N-1:
                    print('inf')
                    return
    #ベルマンフォードする
    d = [INF] * N
    d[0] = 0
    while True:
        update = False
        for e in es:
            if d[e.fr] != INF and d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
                update = True
        if not update: break
    print(-d[N-1])

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 8)
INF = 10 ** 15

class edge:
    def __init__(self, fr, to, cost):
        self.fr, self.to, self.cost = fr, to, cost

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, M = ZZ()
    es = []
    for _ in range(M):
        a, b, c = ZZ()
        a -= 1
        b -= 1
        es.append(edge(a, b, -c))

    #負の閉路検出
    d = [0] * N
    for i in range(N):
        for e in es:
            if d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
                if e.to == N-1 and i == N-1:
                    print('inf')
                    return
    #ベルマンフォードする
    d = [INF] * N
    d[0] = 0
    for _ in range(N-1):
        update = False
        for e in es:
            if d[e.fr] != INF and d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
                update = True
        if not update: break
    print(-d[N-1])

    return

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

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*(n+1)
t = 0
for i in range(k,n+1):
    if i == k:
        x = 1
        for aj in a[i-k:i]:
            x *= aj
            b[i] = x
        t = x
        continue
    else:
        x = b[i-1]/a[i-k-1]*a[i-1]
        #x = 
        if t < x:
            print("Yes")
        else:
            print("No")
        b[i] = x
        t = x
#print(b)


### FIXED CODE ###

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

wa = [0]
for i in range(n):
    wa.append(wa[i]+a[i])

t = wa[k]-wa[0]
for i in range(k+1,n+1):
    if t < wa[i]-wa[i-k]:
        print("Yes")
    else:
        print("No")
    t = wa[i]-wa[i-k]
    # print(wa[i]-wa[i-k],t)
### BUGGY CODE ###

import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def main():
    n = int(input())
    num_list = list(map(int, input().split()))

    ans = 0
    for i in range(n):
        # tmp = num_list[i]
        # num_list[i] = max(num_list)
        # ans = max(ans, fractions.gcd(num_list[i],min(num_list)))
        # num_list[i] = tmp
        li = num_list[:i] + num_list[i + 1:]
        tmp = gcd_list(li)
        if tmp > ans:
            ans = tmp

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import fractions

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def main():
    n = int(input())
    num_list = list(map(int, input().split()))

    left = [0] * (n + 1)
    right = [0] * (n + 1)
    for i in range(n):
        left[i + 1] = (fractions.gcd(left[i],num_list[i]))
        right[n - i - 1] = (fractions.gcd(right[n - i],num_list[n - 1 - i]))
    
    ans = 0
    for i in range(n):
        ans = max(ans,fractions.gcd(left[i],right[i + 1]))

    print(ans)

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

from bisect import*
r=range
n,*t=map(int,open(0).read().split())
m=2**16
x=t[:n]
d=[[bisect(x,y+t[n])-1for y in x]]+[[0]*n for _ in r(m)]
for i in r(m):
  for j in r(n):
    d[i+1][j]=d[i][d[i][j]]
for a in zip(t[n+2::2],t[n+3::2]):
  a,b=sorted(i-1for i in a)
  c=1
  for i in r(m,-1,-1):
    if d[i][a]<b:
      a=d[i][a]
      c+=2**i
  print(c)

### FIXED CODE ###

from math import*
from bisect import*
n,*t=map(int,open(0).read().split())
m=int(log2(n))+1
x=t[:n]
l=t[n]
d=[[bisect(x,y+l)-1for y in x]]+[[0]*n for _ in range(m)]
for i in range(m):
    for j in range(n):
        d[i+1][j]=d[i][d[i][j]]
for a,b in zip(t[n+2::2],t[n+3::2]):
    a-=1
    b-=1
    if b<a:a,b=b,a
    c=1
    for i in range(m,-1,-1):
        if d[i][a]<b:
            a=d[i][a]
            c+=2**i
    print(c)
### BUGGY CODE ###

from itertools import permutations
N = int(input())
A = list(map(int, (input().split())))

ans = 0
for p in permutations(range(N)):
    tmp = 0
    for i in range(N):
        tmp += A[i] * abs(i-p[i])
    ans = max(ans, tmp)

print(ans)


### FIXED CODE ###

import sys
# def input(): return sys.stdin.readline().rstrip()
# input = sys.stdin.readline
input = sys.stdin.buffer.readline

N = int(input())
A = sorted(zip(map(int, (input().split())) ,range(N)), reverse=True)

dp = [[0]*(N+1) for _ in range(N+1)]
ans = 0
for i in range(N):
    for j in range(i+1):
        dp[i+1][j]   = max(dp[i+1][j], dp[i][j] + A[i][0] * abs(A[i][1] - (N-1-(i-j))))
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + A[i][0] * abs(A[i][1] - j))

for i in range(N):
    ans = max(ans, dp[N][i])

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

N = int(input())
# スペース区切りの整数の入力
A = list(map(int, input().split()))

for i in range(N):
	print (A.count(i+1))

### FIXED CODE ###

import collections

N = int(input())
# スペース区切りの整数の入力
A = list(map(int, input().split()))


c = collections.Counter(A)

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

s = input()
q = int(input())

def addflont(s,c):
    return c+s
def addback(s,c):
    return s+c

reverse = 0

for i in range(q):
    t = input()
    if t[0]=="1":
        reverse += 1
    if t[0]=="2":
        if t[2]=="1":
            if reverse%2==0:
                s = addflont(s,t[4])
            else:
                s = addback(s,t[4])
        elif t[2]=="2":
            if reverse%2==0:
                s = addback(s,t[4])
            else:
                s = addflont(s,t[4])

if reverse%2==1:
    print(s[::-1])
else:
    print(s)


### FIXED CODE ###



s = input()
q = int(input())

def addflont(s,c):
    text = "".join([c,s])
    return text
def addback(s,c):
    text = "".join([s,c])
    return text

reverse = 0
r = "";u = ""
for i in range(q):
    t = input()
    if t[0]=="1":
        reverse = reverse^1
    if t[0]=="2":
        if t[2]=="1":
            if reverse==0:
                r = addflont(r,t[4])
            else:
                u = addback(u,t[4])
        elif t[2]=="2":
            if reverse==0:
                u = addback(u,t[4])
            else:
                r = addflont(r,t[4])

s = r + s + u
if reverse==1:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

X = int(input())
P = [i for i in range(10**5)]
for i in range(2,10**5):
    if i in P:
        n = X//i
        for j in range(1,n):
            if 2*(j+1) in P:
                P.remove(2*(j+1))
P.append(100003)
for i in P:
    if i >= X:
        print(i)
        break

### FIXED CODE ###

X =int(input())
def f(n):
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            return False
    return True
for i in range(X,100004):
    if f(i):
        print(i)
        break
### BUGGY CODE ###

def isort(a, n, g):
    global cnt
    for i in range(g, n):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j + g] = a[j]
            j -= g
            cnt += 1
        a[j + g] = v

# input data
n = int(raw_input())
a = []
for i in range(n):
    a.append(int(raw_input()))

# determine m, g
g = [1]
m = 1
while True:
    x = 3 * g[m - 1] + 1
    if x >= n: break
    g.append(x)
    m += 1
g = g[::-1]

# 1 output m
print(m)
# 2 output g
print(' '.join(map(str, g)))

# sort it
cnt = 0
for i in range(m):
    isort(a, n, g[i])

# 3 output cnt
print(cnt)
# 4 output sorted a
for i in range(n):
    print(a[i])

### FIXED CODE ###

import sys
 
def isort(a, n, g):
    global cnt
    for i in range(g, n):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j + g] = a[j]
            j -= g
            cnt += 1
        a[j + g] = v
 
# input data
n = int(sys.stdin.readline())
a = []
for i in range(n):
    a.append(int(sys.stdin.readline()))
 
# determine m, g
g = [1]
m = 1
while True:
    x = 3 * g[m - 1] + 1
    if x >= n: break
    g.append(x)
    m += 1
g = g[::-1]
 
# 1 output m
print(m)
# 2 output g
print(' '.join(map(str, g)))
 
# sort it
cnt = 0
for i in range(m):
    isort(a, n, g[i])
 
# 3 output cnt
print(cnt)
# 4 output sorted a
print('\n'.join(map(str, a)))
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, Q = MAP()
LR = [LIST() for _ in range(M)]

x = [[0]*N for _ in range(N)]
for L, R in LR:
	x[L-1][R-1] += 1

pq = [LIST() for _ in range(Q)]

C = [[0]*N for _ in range(N)]

for i in range(N):
	tmp = 0
	for j in range(N):
		tmp += x[i][j]
		C[i][j] = tmp

for p, q in pq:
	p = p-1
	q = q-1
	ans = 0
	for i in range(p, q+1):
		if p-1 <= -1:
			ans += C[i][q]
		else:
			ans += C[i][q]-C[i][p-1]
	print(ans)



### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
	N, M, Q = MAP()
	LR = [LIST() for _ in range(M)]

	x = [[0]*N for _ in range(N)]
	for L, R in LR:
		x[L-1][R-1] += 1

	pq = [LIST() for _ in range(Q)]

	C = [[0]*N for _ in range(N)]

	for i in range(N):
		tmp = 0
		C[i] = list(accumulate(x[i]))

	for p, q in pq:
		p = p-1
		q = q-1
		ans = 0
		for i in range(p, q+1):
			if p-1 <= -1:
				ans += C[i][q]
			else:
				ans += C[i][q]-C[i][p-1]
		print(ans)

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

N, Q = [int(_) for _ in input().split()]
S = input()
l_r_list = [[int(_) for _ in input().split()] for _ in range(Q)]
ans = []

for l, r in l_r_list:
    S_lr = S[l - 1:r]
    ans.append(str(S_lr.count("AC")))

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

### FIXED CODE ###

N, Q = [int(_) for _ in input().split()]
S = input()
l_r_list = [[int(_) for _ in input().split()] for _ in range(Q)]

AC_accumulation = [0]

for i in range(1, N):
    if S[i] == "C" and S[i - 1] == "A":
        AC_accumulation.append(AC_accumulation[-1] + 1)
    else:
        AC_accumulation.append(AC_accumulation[-1])


ans = []
for l, r in l_r_list:
    ans.append(str(AC_accumulation[r - 1] - AC_accumulation[l - 1]))

print("\n".join(ans))
### BUGGY CODE ###

"""
dp[i][j][k] => i行目、j列のマスまで見る。k個取る時の最高値。
"""
R,C,K = map(int,input().split())
items = [[0]*C for _ in range(R)]
for _ in range(K):
    r,c,v = map(int,input().split())
    items[r-1][c-1] = v

dp = [[[0]*4 for _ in range(C)]for _ in range(R)]

for i in range(R):
    for j in range(C):
        v = items[i][j]
        if i == 0 and j == 0 and v != 0:
            dp[i][j][1] = v

        #上から降りてくる場合の価値を求める
        if i != 0:
            #i行目j列のアイテムを取らない場合
            dp[i][j][0] = max(dp[i-1][j])
            #i行目j列のアイテムを取る場合
            if v!=0:
                dp[i][j][1] = max(dp[i-1][j]) + v

        #左から入ってくる場合の価値を求める
        if j != 0:
            if v == 0:
                for k in range(4):
                    dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
            else:
                for k in range(1,4):
                    dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k],dp[i][j-1][k-1]+v)
print(max(dp[-1][-1]))

### FIXED CODE ###

"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

    for _ in range(K):
        r,c,v = map(int,input().split())
        items[r-1][c-1] = v

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                #左から入る場合のシミュレート
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print(max(dp[-1]))
main()
### BUGGY CODE ###

from collections import Counter
n = int(input())
c = Counter(map(int, input().split()))
dp = [[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
for i in (range(n+1)):
    for j in (range(n+1)):
        for k in (range(n+1)):
            non_zero = i+j+k
            if non_zero == 0:
                continue
            dp[i][j][k] = n/non_zero
            if 0 <= i-1 and j+1 <= n:
                dp[i][j][k] += dp[i-1][j+1][k]*i/non_zero
            if 0 <= j-1 and k+1 <= n:
                dp[i][j][k] += dp[i][j-1][k+1]*j/non_zero
            if 0 <= k-1:
                dp[i][j][k] += dp[i][j][k-1]*k/non_zero
print(dp[c[3]][c[2]][c[1]])


### FIXED CODE ###

from collections import Counter
n = int(input())
c = Counter(map(int, input().split()))
dp = [[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]

for i in range(n+1):
    for j in range(n+1-i):
        for k in range(n+1-i-j):
            non_zero = i+j+k
            if non_zero == 0:
                continue
            dp[i][j][k] = n
            if 0 <= i-1 and j+1 <= n:
                dp[i][j][k] += dp[i-1][j+1][k]*i
            if 0 <= j-1 and k+1 <= n:
                dp[i][j][k] += dp[i][j-1][k+1]*j
            if 0 <= k-1:
                dp[i][j][k] += dp[i][j][k-1]*k
            dp[i][j][k] /= non_zero

print(dp[c[3]][c[2]][c[1]])
### BUGGY CODE ###

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

A=list(map(int,input().split()))
A.sort()
dc=[]

for i in range(M):
    B,C=map(int,input().split())
    dc.append([B,C])

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

i=0
for l in dc:
    B,C=l
    while B>0:
        if i<N and A[i]<C:
            A[i]=C
            B-=1
            i+=1
        elif i<N:
            i+=1
            break

print(sum(A))

### FIXED CODE ###

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

A=list(map(int,input().split()))
A.sort()
dc=[]

for i in range(M):
    B,C=map(int,input().split())
    dc.append([B,C])

dc.sort(key=lambda x: x[1],reverse=True)
bf=False
i=0
for l in dc:
    B,C=l
    if bf:
        break
    while B>0:
        if i<N and A[i]<C:
            A[i]=C
            B-=1
            i+=1
        else:
            bf=True
            break


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

from collections import deque
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]
# 目印置くリスト
me = [0 for _ in range(n+1)]
me[1] = 1
miti = [[] for _ in range(n+1)]
tansaku = [0 for i in range(n+1)]
tansaku[1]=1
for i,j in l:
  miti[j].append(i)
  miti[i].append(j)
a = deque()
for i in miti[1]:
  a.append(i)
  me[i] = 1
while len(a)!=0:
#  print(a)
  w = a.popleft()
  tansaku[w] = 1
  for j in miti[w]:
    if tansaku[j]==0 and j not in a:
          a.append(j) 
          me[j] = w
#  print(w,tansaku,me)
  
print("Yes")
for i in range(len(miti)-2):
  print(me[i+2])

### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]
# 目印置くリスト
me = [0 for _ in range(n+1)]
me[1] = 1
miti = [[] for _ in range(n+1)]
tansaku = [0 for i in range(n+1)]
tansaku[1]=1
for i,j in l:
  miti[j].append(i)
  miti[i].append(j)
a = deque()
for i in miti[1]:
  a.append(i)
  me[i] = 1
  tansaku[i]=1
while len(a)!=0:
#  print(a)
  w = a.popleft()
  for j in miti[w]:
    if tansaku[j]==0 :
          a.append(j) 
          tansaku[j] = 1
          me[j] = w
 # print(w,tansaku,me,a)
  
print("Yes")
for i in range(len(miti)-2):
  print(me[i+2])
### BUGGY CODE ###

s = input()

count = 0
while True:
    s0 = s
    s = s.replace("10","",1)
    if s0 != s:
        count += 2
        #print(s)
    else:
        s1 = s
        s = s.replace("01","",1)
        if s1 != s:
            count += 2
            #print(s)
        else:
            break

#print(s)
print(count)


### FIXED CODE ###

s = input()

s0 = s.count("0")
s1 = s.count("1")
#print(s0)
#print(s1)
print(len(s)-(max(s0,s1)-min(s0,s1)))
### BUGGY CODE ###

N = int(input())

a_list = list(map(int,input().split()))
a_n_list = []
for i in range(N):
    a_n_list.append([a_list[i],i+1])
a_n_list.sort()
ans = ""
for i in range(N):
    ans = ans + str(a_n_list[i][1]) + " "
print(ans[0:-1])

### FIXED CODE ###

N = int(input())

a_list = list(map(int,input().split()))
a_n_list = []
for i in range(N):
    a_n_list.append([a_list[i],i+1])
a_n_list.sort()
ans = ""
for i in range(N):
    print(a_n_list[i][1], end=" ")
### BUGGY CODE ###

from heapq import heappush, heappop

def prim_heap(edges, n):
    visited = [False] * n
    heap = []
    start = 0
    for e in edges[start]:
        heappush(heap, e)
    visited[start] = True

    res = 0
    while heap:
        cost, v = heappop(heap)
        if visited[v]:
            continue
        visited[v] = True
        res += cost
        for c,u in edges[v]:
            if visited[u]:
                continue
            heappush(heap, (c,u))
    # print(visited)
    return res if sum(visited) == n else -1

def warshall(d, n):
    e = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # print(d[i][k], d[k][j], d[i][j])
                if i == k or k == j:
                    continue
                if d[i][k] + d[k][j] < d[i][j]:
                    e[i][k] = 0
                    e[k][j] = 0
                    e[k][i] = 0
                    e[j][k] = 0
                if d[i][k] + d[k][j] == d[i][j]:
                    # print(d[i][k], d[k][j], d[i][j], i,j,k)
                    e[i][j] = 0
                    e[j][i] = 0
    return e
    
import copy
n = int(input())
edges = []

graph = [list(map(int, input().split())) for i in range(n)]
e = warshall(graph, n)
# print(e)
edge_list = [[] for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j] > 0:
            edge_list[i].append((e[i][j], j))
        if j > i and e[i][j]:
            ans += e[i][j]

print(ans if prim_heap(edge_list, n) != -1 else -1)


### FIXED CODE ###

def warshall(d, n):
    e = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # print(d[i][k], d[k][j], d[i][j])
                if i == k or k == j:
                    continue
                if d[i][k] + d[k][j] < d[i][j]:
                    return []
                if d[i][k] + d[k][j] == d[i][j]:
                    # print(d[i][k], d[k][j], d[i][j], i,j,k)
                    e[i][j] = 0
                    e[j][i] = 0
    return e
    
import copy
n = int(input())
edges = []

graph = [list(map(int, input().split())) for i in range(n)]
e = warshall(graph, n)
if e == []:
    print(-1)
    exit()
# print(e)
edge_list = [[] for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j] > 0:
            edge_list[i].append((e[i][j], j))
        if j > i and e[i][j]:
            ans += e[i][j]

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

import sys
N, M = map(int, input().split())
validJobSalary = [[] for _ in range(M + 1)]  # a[k]には最終日のk日前時点で働いた場合に最終日までに報酬が得られる仕事の報酬リストが入っている
ans = 0
salaryForCurrentlyAvailableJobs = []
for line in sys.stdin:
    A, B = map(int, line.split())
    if A <= M:
        validJobSalary[A].append(B)

for salaryList in validJobSalary:
    salaryForCurrentlyAvailableJobs.extend(salaryList)
    if salaryForCurrentlyAvailableJobs:
        highest = max(salaryForCurrentlyAvailableJobs)
        ans += highest
        salaryForCurrentlyAvailableJobs.remove(highest)

print(ans)


### FIXED CODE ###

import sys
import heapq

N, M = list(map(int, input().split()))
jobs = []
for line in sys.stdin:
    A, B = map(int, line.split())
    if A > M:
        continue
    jobs.append((A, B))

jobs.sort(reverse=True)

q = []
ans = 0
for i in range(1, M + 1):
    while jobs and jobs[-1][0] <= i:
        A, B = jobs.pop()
        heapq.heappush(q, -B)

    if q:
        ans += -heapq.heappop(q)
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
h, w, m = map(int, input().split())
bom_set = set()
h_dict = {}
w_dict = {}
for i in range(m):
    hh, ww = map(int, input().split())
    bom_set.add(tuple([hh, ww]))
    if hh in h_dict:
        h_dict[hh] += 1
    else:
        h_dict[hh] = 1
    if ww in w_dict:
        w_dict[ww] += 1
    else:
        w_dict[ww] = 1
h_max_count = max(h_dict.values())
w_max_count = max(w_dict.values())
flag = 0
for hh in h_dict:
    if h_dict[hh] < h_max_count:
        continue
    for ww in w_dict:
        if w_dict[ww] < w_max_count:
            continue
        if tuple([hh, ww]) not in bom_set:
            flag = 1
            break
    if flag == 1:
        break
if flag == 1:
    print(h_max_count + w_max_count)
else:
    print(h_max_count + w_max_count - 1)

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
h, w, m = map(int, input().split())
bom_set = set()
h_dict = {}
w_dict = {}
for i in range(m):
    hh, ww = map(int, input().split())
    bom_set.add(tuple([hh, ww]))
    if hh in h_dict:
        h_dict[hh] += 1
    else:
        h_dict[hh] = 1
    if ww in w_dict:
        w_dict[ww] += 1
    else:
        w_dict[ww] = 1
h_max_count = max(h_dict.values())
w_max_count = max(w_dict.values())
hh_dict = {}
ww_dict = {}
for hh in h_dict:
    if h_dict[hh] == h_max_count:
        hh_dict[hh] = h_max_count
for ww in w_dict:
    if w_dict[ww] == w_max_count:
        ww_dict[ww] = w_max_count
flag = 0
for hh in hh_dict:
    for ww in ww_dict:
        if tuple([hh, ww]) not in bom_set:
            flag = 1
            break
    if flag == 1:
        break
if flag == 1:
    print(h_max_count + w_max_count)
else:
    print(h_max_count + w_max_count - 1)
### BUGGY CODE ###

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

score = 1
for i in range(K):
    score *= A[i]

for i in range(K,N):
    tmp = score*A[i]/A[i-K]
    if score < tmp:
        print("Yes")
    else:
        print("No")
    scpre = tmp


### FIXED CODE ###

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

for i in range(K,N):
    if A[i-K] < A[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n=int(input())
a=[]

for i in range(n):
  word=input()
  if word not in a:
    a.append(word)
print(len(a))

### FIXED CODE ###

n=int(input())
a=[]
 
for i in range(n):
  word=input()
  a.append(word)
print(len(set(a)))