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

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def lm(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def gm(a, b):
    return a * b // lm(a, b)


def Prim(N):
    P = []
    M = int(N ** 0.5) + 10
    F = [False, False] + [True] * M
    for n in range(2, M):
        if not F[n]:
            continue
        P.append(n)
        for i in range(n, len(F), n):
            F[i] = False
    
    return P
 

def ps(a, P):
    d = {}
    for p in P:
        while a % p == 0:
            d[p] = d.setdefault(p, 0) + 1
            a //= p
        
        if a == 1:
            break
    
    if a != 1:
        d[a] = d.setdefault(a, 0) + 1
    return d


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()
    P = Prim(max(A))
    DA = [ps(a, P) for a in A]
    
    D = {}
    for d in DA:
        for i, v in d.items():
            D[i] = max(D.setdefault(i, 0), v)

    res = 0
    for d in DA:
        b = 1
        for i, v in D.items():
            b = b * (i ** max(0, v - d.setdefault(i, 0))) % mod

        res = (res + b) % mod

    print(res)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def g(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    B = 1
    for a in A:
        B *= a // g(B, a)
    
    print(sum(B // a for a in A) % mod)


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

#D
s_list=list(input())
q=int(input())

for i in range(q):
    ope=input().split()
    if ope[0]=='1':
        s_list.reverse()
    else:
        if ope[1]=='1':
            s_list.insert(0,ope[2])
        else:
            s_list.append(ope[2])
print(''.join(s_list))

### FIXED CODE ###

#D
s_list=list(input())
q=int(input())
r=0
sl_list=[]
for i in range(q):
    ope=input().split()
    if ope[0]=='1':
        r+=1
    else:
        if (int(ope[1])+r)%2 == 1:
            sl_list.append(ope[2])
        else:
            s_list.append(ope[2])
sl_list.reverse()
s_list=sl_list + s_list
if r%2 !=0:
    s_list.reverse()
print(''.join(s_list))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M, P = map(int, input().split())
    g = [[] for _ in range(N+1)]
    g2 = [[] for _ in range(N+1)]
    data = [list(map(int, input().split())) for _ in range(M)]
    for a, b, _ in data:
        g[b].append(a)
        g2[a].append(b)

    visit = [False]*(N+1)
    visit2 = [False]*(N+1)

    queue = [N]
    while len(queue) > 0:
        nextqueue = []
        for now in queue:
            visit[now] = True
            for next in g[now]:
                if not visit[next]:
                    nextqueue.append(next)
        queue = nextqueue[:]

    queue = [1]
    while len(queue) > 0:
        nextqueue = []
        for now in queue:
            visit2[now] = True
            for next in g2[now]:
                if not visit2[next]:
                    nextqueue.append(next)
        queue = nextqueue[:]




    for i in range(1, N+1):
        visit[i] = visit[i] and visit2[i]


    INF = 1000000001
    d = [(-1)*INF for i in range(N+1)]
    d[1] = 0

    for i in range(N):
        d_N = [d[i] for i in range(1, N+1) if visit[i]]
        for j in range(M):
            a = data[j][0]
            b = data[j][1]
            c = data[j][2]
            d[b] = max(d[b], d[a]+c-P)
        if i == N-1:
            if d_N != [d[i] for i in range(1, N+1) if visit[i]]:
                ans = -1

            else:
                ans = d[N]

    if ans == -1:
        print(-1)
    else:
        print(max(0, ans))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import queue
input = sys.stdin.readline

def main():
    N, M, P = map(int, input().split())
    g = [[] for _ in range(N+1)]
    g2 = [[] for _ in range(N+1)]
    data = [list(map(int, input().split())) for _ in range(M)]
    for a, b, _ in data:
        g2[b].append(a)
        g[a].append(b)

    visit = [False]*(N+1)
    visit2 = [False]*(N+1)

    q = queue.Queue()
    q.put(1)
    visit[1] = True
    while (not q.empty()):
        now = q.get()
        for next in g[now]:
            if not visit[next]:
                visit[next] = True
                q.put(next)

    q = queue.Queue()
    q.put(N)
    visit2[N] = True
    while (not q.empty()):
        now = q.get()
        for next in g2[now]:
            if not visit2[next]:
                visit2[next] = True
                q.put(next)

    for i in range(1, N+1):
        visit[i] = visit[i] and visit2[i]


    INF = 1000000001
    d = [(-1)*INF for i in range(N+1)]
    d[1] = 0

    for i in range(N):
        d_N = [d[i] for i in range(1, N+1) if visit[i]]
        for j in range(M):
            a = data[j][0]
            b = data[j][1]
            c = data[j][2]
            d[b] = max(d[b], d[a]+c-P)
        if i == N-1:
            if d_N != [d[i] for i in range(1, N+1) if visit[i]]:
                ans = -1

            else:
                ans = d[N]

    if ans == -1:
        print(-1)
    else:
        print(max(0, ans))

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

from sys import stdin

def main():
    n, k = list(map(int, input().split()))
    A = list(map(int, stdin.readline().split()))
    roots = [1]
    position = 0
    while True:
        position = A[roots[-1]-1]
        if position in roots:
            break
        roots.append(position)

    x = roots.index(position)
    y = len(roots) - x

    if k <= x:
        print(roots[k])
    elif k > x:
        print(roots[x + ((k-x) % y)])





if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin


def main():
    n, k = list(map(int, input().split()))
    A = list(map(int, stdin.readline().split()))
    roots = [1]
    position = 0
    for _ in range(n):
        position = A[roots[-1]-1]
        A[roots[-1]-1] = - position
        if position < 0:
            break
        roots.append(position)

    x = roots.index(-position)
    y = len(roots) - x

    if k <= x:
        print(roots[k])
    elif k > x:
        print(roots[x + ((k-x) % y)])


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

#!/usr/bin/env python3
 
import sys
from collections import defaultdict
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

### FIXED CODE ###

import bisect
s = input().rstrip()
t = input().rstrip()

a_ord = ord("a")
ch_place = [[] for _ in range(26)]
for i, ch in enumerate(s):
    ch_place[ord(ch) - a_ord].append(i)

# print(ch_place)

count = 0
idx = -1 
for ch in t:
    ch_num = ord(ch) - a_ord
    if len(ch_place[ch_num]) == 0:
        print(-1)
        exit()
    place = bisect.bisect_right(ch_place[ch_num], idx)
    # print(ch_place[ch_num], idx, place)
    if place == len(ch_place[ch_num]):
        idx = ch_place[ch_num][0]
        count += 1
    else:
        idx = ch_place[ch_num][place]

# print(count, idx)
print(count * len(s) + idx + 1)
### BUGGY CODE ###

S = str(input())

# dp[i][j] := i文字目（1-index)まで割り算した余りがjになるような'?'の置き換えが何通りあるか。
dp = [[0]*13 for _ in range(100001)]

S_length = len(S)
MOD = 1000000007
dp[0][0] = 1  # dpの初期化。0文字目までの割り算の余りが0になるような置き換えが1通りあると考える。

# 今、計算をしているのがi文字目, dpのiは1-indexだが、Sへのアクセスは0インデックスで行う
for i in range(1, S_length+1):
    for remain in range(13):  # i-1文字目まで計算した余りを決め打ちしているループ変数remain
        if S[i-1] == '?':  # i文字目が'?'であったらそれぞれをjに置き換えて計算
            for j in range(10):
                next_remain = (remain*10+j) % 13  # (i-1)文字目までの余りがremainで，i文字目の'?'に置き換えた場合の，i文字目まで計算した余り

                # dpの遷移
                dp[i][next_remain] += dp[i-1][remain]
                dp[i][next_remain] %= MOD
        else:
            next_remain = (remain*10 + int(S[i-1])) % 13
            # dpの遷移
            dp[i][next_remain] += dp[i-1][remain]
            dp[i][next_remain] %= MOD

print(dp[S_length][5])  # 答えはS_length文字目(つまり最後の文字)まで計算した余りが5になるような'?'の置き換えが何通りあるか


### FIXED CODE ###

S = str(input())

# dp[i][j] := i文字目（1-index)まで割り算した余りがjになるような'?'の置き換えが何通りあるか。
dp = [[0]*13 for _ in range(100001)]

S_length = len(S)
MOD = 1000000007
dp[0][0] = 1  # dpの初期化。0文字目までの割り算の余りが0になるような置き換えが1通りあると考える。

# 今、計算をしているのがi文字目, dpのiは1-indexだが、Sへのアクセスは0インデックスで行う
for i in range(1, S_length+1):
    for remain in range(13):  # i-1文字目まで計算した余りを決め打ちしているループ変数remain
        if S[i-1] == '?':  # i文字目が'?'であったらそれぞれをjに置き換えて計算
            for j in range(10):
                next_remain = (remain*10+j) % 13  # (i-1)文字目までの余りがremainで，i文字目の'?'に置き換えた場合の，i文字目まで計算した余り

                # dpの遷移
                dp[i][next_remain] += dp[i-1][remain]
                dp[i][next_remain] %= MOD
        else:
            next_remain = (remain*10 + int(S[i-1])) % 13
            # dpの遷移
            dp[i][next_remain] += dp[i-1][remain]
            dp[i][next_remain] %= MOD

print(dp[S_length][5])  # 答えはS_length文字目(つまり最後の文字)まで計算した余りが5になるような'?'の置き換えが何通りあるか
### BUGGY CODE ###

import math

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

def C(N,P):
    if N == 1: return P
    a=P
    N1=2
    while N >= N1:
        N1*=2
        a=math.sqrt(a)

    res=1
    for i in range(1,int(a)+2):
        if P % i**N: continue
        res = i
    return res

print(C(n,p))

### FIXED CODE ###

n,p = list(map(int,input().split())) 
i = a = o = 1
m = round(p**(1/n))
for i in range(m,0,-1):
    a = i**n
    if p%a==0:
        print(i)
        exit()
### BUGGY CODE ###

nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]

gates = [list(map(lambda x: int(x), input().split())) for i in range(m)]

keys = [i+1 for i in range(n)]
key_count = [0 for i in range(n)]

for gate in gates:
  new_key = keys.copy()

  for key in keys:
    if (key >= gate[0] and key <= gate[1]):
      key_count[key-1] += 1
    else:
      new_key.remove(key)
  keys = new_key

print(len(keys))

### FIXED CODE ###

nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]

gates = [list(map(lambda x: int(x), input().split())) for i in range(m)]

first_max = 0
second_min = 100001
for gate in gates:
  first_max = max(first_max, gate[0])
  second_min = min(second_min, gate[1])

answer = second_min - first_max + 1
if (answer <= 0):
  print(0)
else:
  print(answer)
### BUGGY CODE ###


import collections
n,ais = int(raw_input()), map(int, raw_input().split())
cc = collections.Counter()
for ai in ais:
	if ai % 4 == 0: cc[0] += 1
	elif ai % 2 == 0: cc[1] += 1
	else: cc[2] += 1

q = collections.deque()
h = {0:[2,1,0], 1:[1,0], 2:[0]} 
while(n):
	if len(q) == 0:
		for u in range(3)[::-1]:
			if cc[u] > 0:
				q.append(u)
				cc[u]-=1
				n -=1
				break
		if len(q) == 0: break
	else:
		booll = False
		for u in h[q[-1]] + [-1]:
			if u == -1:
				boool = True
				break
			if cc[u]:
				q.append(u)
				cc[u]-=1
				n-=1
				break
		if booll:
			break

print 'Yes' if n == 0 else 'No'

### FIXED CODE ###


n,ais = int(raw_input()), map(int, raw_input().split())
import collections
cc = collections.Counter()
for ai in ais:
	if ai % 4 == 0: cc[0] += 1
	elif ai % 2 == 0: cc[1] += 1
	else: cc[2] += 1

q = collections.deque()
while(n):
	if len(q) == 0:
		for u in range(3)[::-1]:
			if cc[u] > 0:
				q.append(u)
				cc[u]-=1
				n -=1
				break
		if len(q) == 0: break
	else:
		if q[-1] == 0:
			if cc[2]:
				q.append(2)
				cc[2]-=1
				n-=1
			elif cc[1]:
				q.append(1)
				cc[1]-=1
				n-=1
			elif cc[0]:
				q.append(0)
				cc[0]-=1
				n-=1
			else:
				break
		elif q[-1] == 2:
			if cc[0] == 0:
				break
			else:
				q.append(0)
				cc[0]-=1
				n-=1
		elif q[-1] == 1:
			if cc[1] > 0:
				q.append(1)
				cc[1]-=1
				n-=1
			else:
				break

print 'Yes' if n == 0 else 'No'
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
K = int(input())
a = list(range(1,K+1))
b = list(range(1,K+1))
c = list(range(1,K+1))
Sum = 0
for i in a :
    for j in b:
        for k in c:
            S = gcd(i,j,k)
            Sum = Sum + S
print(Sum)

### FIXED CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
K = int(input())
a = list(range(1,K+1))
b = list(range(1,K+1))
c = list(range(1,K+1))
Sum = 0
for i in a :
    for j in b:
        for k in c:
            S = gcd(i,j,k)
            Sum = Sum + S
print(Sum)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque
from heapq import heappush,heappop,heapify

N=input()
AL=defaultdict(lambda: set())
IN=defaultdict(lambda: 0)
BEGIN=set()

for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(N-2):
		x=i+1
		x_next=i+1
		y=A[j]
		y_next=A[j+1]
		#print x,y,x_next,y_next
		if x>y: x,y=y,x
		if x_next>y_next: x_next,y_next=y_next,x_next
		IN[(x_next,y_next)]+=1
		AL[(x,y)].add((x_next,y_next))

		if j==0:
			BEGIN.add((x,y))

hq=[]

for x,y in BEGIN:
	if IN[(x,y)]==0:
		heappush(hq, (0,x,y))


DAY=defaultdict(lambda: 1)	#距離

ans=-1
while hq:
	cost,fro_x,fro_y=heappop(hq)
	fro=(fro_x,fro_y)
	for to in AL[fro]:
		alt=DAY[fro]+1
		if DAY[to]<alt:
			ans=max(ans,alt)
			DAY[to]=alt
			heappush(hq,(alt,to[0],to[1]))

print ans

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
from collections import defaultdict,deque

N=input()
A=[[]]+[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
C=defaultdict(lambda: 0)

Now=[ 0 for _ in range(N+1)]
game=set()
next_game=set()

for i in range(1,N+1):
	a=i
	b=A[i][0]
	if a>b: a,b=b,a
	game.add((a,b))

day=0

while game:
	next_game=set()
	Visit=defaultdict(lambda: None) 

	for x,y in game:
		now_x=Now[x]
		now_y=Now[y]

		xopp=A[x][now_x]
		yopp=A[y][now_y]

		if (x,y)==(yopp,xopp) and Visit[x] is None and Visit[y] is None:
			Visit[x]=1
			Visit[y]=1
			if now_x<N-2:
				now_x+=1
				Now[x]=now_x
				x_nextopp=A[x][now_x]
				if x_nextopp<x: x,x_nextopp=x_nextopp,x
				next_game.add((x,x_nextopp))

			if now_y<N-2:
				now_y+=1
				Now[y]=now_y
				y_nextopp=A[y][now_y]
				if y_nextopp<y: y,y_nextopp=y_nextopp,y
				next_game.add((y,y_nextopp))

	game=next_game
	day+=1


for i in range(1,N+1):
	if Now[i] != N-2:
		print -1
		quit()
else:
	print day
### BUGGY CODE ###

#AからBまでの排他的論理和を出す

a,b=map(int,input().split())
count=0
for i in range(a,b+1):
	count=count^i

print(count)


### FIXED CODE ###

#AからBの排他的論理和　計算短縮版

import math
a,b=map(int,input().split())
c=0
list=[]
d=0


number_of_1=0
sum_of_1=0
nose=0
tail=0

if a%2==0:
	number_of_1=(b+1-a)//2
else:
	number_of_1=(b-a)//2

sum_of_1=number_of_1 % 2

if a%2==0:
	nose=0
else:
	nose=a

if b%2==0:
	tail=b
else:
	tail=0

print(nose^tail^sum_of_1)
### BUGGY CODE ###

# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
STX = [tuple(lr()) for _ in range(N)]
STX.sort(key=lambda x: x[2], reverse=True)
event = []
for s, t, x in STX:
    s = max(-1, s-x)
    t = max(0, t-x)
    event.append((s, 0, x))
    event.append((t, -1, x))

answer = [None] * Q
for i in range(Q):
    d = ir()
    event.append((d, 1, i))

event.sort()
cur = []
used = set()
for a, b, c in event:
    if b == 0:
        if c in used:
            used.remove(c)
        heappush(cur, c)
    elif b == -1:
        used.add(c)
    elif b == 1:
        while cur and cur[0] in used:
            heappop(cur)
        if cur:
            answer[c] = cur[0]
        else:
            answer[c] = -1

print('\n'.join(map(str, answer)))
# 19

### FIXED CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
STX = [tuple(lr()) for _ in range(N)]
event = []
for s, t, x in STX:
    event.append((s-x, 0, x))
    event.append((t-x, -1, x))

for i in range(Q):
    d = ir()
    event.append((d, 1, i))

event.sort()
answer = [-1] * Q
cur = set()
flag = False
INF = 10 ** 10
min_x = INF
for a, b, c in event:
    if b == 0:
        cur.add(c)
        if c < min_x:
            min_x = c
            flag = True
    elif b == -1:
        cur.remove(c)
        if min_x == c:
            flag = False
    elif b == 1:
        if cur:
            if not flag:
                min_x = min(cur)
                flag = True
            answer[c] = min_x

print('\n'.join(map(str, answer)))
# 19
### BUGGY CODE ###

def main():
    x,y = map(int,input().split())
    p = list(map(int,input().split()))

    bigNumber = 0

    for i in range(x-y+1):

        number = sum(p[i:i+y])

        if sum(p[i:i+y]) > bigNumber:
            bigNumber = number

    print((bigNumber + y) / 2)

main()


### FIXED CODE ###

def main():
    x,y = map(int,input().split())
    p = list(map(int,input().split()))

    number = sum(p[0:y])
    bigNumber = number

    for i in range(x-y):

        number = number - p[i] + p[i+y]

        if number > bigNumber:
            bigNumber = number

    print((bigNumber + y) / 2)

main()
### BUGGY CODE ###

num = int(input())
nums = input().split()

seki = 1
for item in nums:
  seki *= int(item)
  
if seki > 10**18:
  print(-1)
else:
  print(seki)

### FIXED CODE ###

num = int(input())
nums = input().split()

zero_flag = False
for item in nums:
  if item == '0':
    zero_flag = True
    break
    
if zero_flag:
  seki = 0
else:
  seki = 1
  for item in nums:
    seki *= int(item)
    if seki > 10**18:
      seki = -1
      break

print(seki)
### BUGGY CODE ###

def main():
    import itertools

    n = int(input())
    s = input()
    print(len(set(itertools.combinations(s, 3))))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import itertools
    import re

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

    cnt = 0
    for key in itertools.product('0123456789', repeat=3):
        key1, key2, key3 = map(str, key)
        if key1 in s:
            key1_idx = s.find(key1)
            if key2 in s[key1_idx+1:]:
                key2_idx = key1_idx + s[key1_idx+1:].find(key2) + 1
                if key3 in s[key2_idx+1:]:
                    cnt += 1

    print(cnt)


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

from itertools import combinations, product
from math import factorial

def nCr(n, r):
  return int(factorial(n) / factorial(n - r) / factorial(r))

n = int(input())
k = int(input())
size = len(str(n))
count = 0 if k > size - 1 else (nCr(size - 1, k) * (9 ** k))
if k == 1:
  count += sum(i * (10 ** (size - 1)) <= n for i in range(1, 10))
else:
  for digits in combinations(range(size - 1), k - 1):
    digits = [size - 1] + list(digits)
    count += sum(
      sum(num * (10 ** digit) for num, digit in zip(nums, digits)) <= n
      for nums in product(range(1, 10), repeat=k)
    )
print(count)


### FIXED CODE ###

from itertools import combinations, product
from math import factorial

def nCr(n, r):
  return int(factorial(n) / factorial(n - r) / factorial(r))

n = int(input())
k = int(input())
size = len(str(n))
count = 0 if k > size - 1 else nCr(size - 1, k) * (9 ** k)
if k == 1:
  count += sum(i * (10 ** (size - 1)) <= n for i in range(1, 10))
else:
  first = int(str(n)[0])
  count += 0 if k > size else (first - 1) * nCr(size - 1, k - 1) * (9 ** (k - 1))
  for digits in combinations(range(size - 1), k - 1):
    count += sum(
      sum(num * (10 ** digit) for num, digit in zip(nums, digits)) <= n % (10 ** (size - 1))
      for nums in product(range(1, 10), repeat = k - 1)
    )
print(count)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

import queue
        
N, Q = map(int, input().rstrip().split())
e = [list(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(N-1)]
q = [list(map(int, input().rstrip().split())) for _ in range(Q)]

v2e = [set() for _ in range(N)]
for a, b in e:
    v2e[a].add(b)
    v2e[b].add(a)

v = [0] * N
for i in range(Q):
    v[q[i][0]-1] += q[i][1]
    
que = queue.Queue()
que.put((0, 0))
f = [False] * N
f[0] = True
while que.qsize() > 0:
    a, b = que.get()
    v[a] += b
    for c in v2e[a]:
        if f[c] == False:
            que.put((c, v[a]))
            f[c] = True
            
print(' '.join(list(map(str, v))))

### FIXED CODE ###

# coding: utf-8
# Your code here!

import queue
import sys
input = sys.stdin.readline
        
N, Q = map(int, input().rstrip().split())
e = [list(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(N-1)]
q = [list(map(int, input().rstrip().split())) for _ in range(Q)]

v2e = [set() for _ in range(N)]
for a, b in e:
    v2e[a].add(b)
    v2e[b].add(a)

v = [0] * N
for i in range(Q):
    v[q[i][0]-1] += q[i][1]
    
que = queue.Queue()
que.put((0, 0))
f = [False] * N
f[0] = True
while que.qsize() > 0:
    a, b = que.get()
    v[a] += b
    for c in v2e[a]:
        if f[c] == False:
            que.put((c, v[a]))
            f[c] = True
            
print(' '.join(list(map(str, v))))
### BUGGY CODE ###

# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, M, ABs):
    ans = 0
    schedule = [0] * M
    max_start_day = [M - i for i in range(M + 1)]
    ABs.sort(key=lambda x: x[1], reverse=True)
    for A, B in ABs:
        if A > M:
            continue
        work_day = max_start_day[A]
        if work_day < 0:
            continue
        flg = False
        while schedule[work_day] != 0:
            work_day -= 1
            if work_day < 0:
                flg = True
                break
        if flg:
            max_start_day[A] = work_day
            continue
        ans += B
        schedule[work_day] = B
        max_start_day[A] = work_day - 1
    print(ans)


if __name__ == '__main__':
    N, M = map(int, input().split())
    ABs = [[int(i) for i in input().split()] for _ in range(N)]

    # from random import randint
    # N, M = 10 ** 5, 10 ** 5
    # ABs = [[randint(1, 10 ** 5), randint(1, 10 ** 4)] for _ in range(10 ** 5)]

    solve(N, M, ABs)

### FIXED CODE ###

# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, M, ABs):
    ans = 0
    schedule = [0] * M
    max_start_day = [M - i for i in range(M + 1)]
    ABs.sort(key=lambda x: x[1], reverse=True)
    for A, B in ABs:
        if A > M:
            continue
        work_day = max_start_day[A]
        if work_day < 0:
            continue
        flg = False
        while schedule[work_day] != 0:
            work_day -= 1
            if work_day < 0:
                flg = True
                break
        if flg:
            max_start_day[A] = work_day
            continue
        ans += B
        schedule[work_day] = B
        max_start_day[A] = work_day - 1
    print(ans)


if __name__ == '__main__':
    N, M = map(int, input().split())
    ABs = [[int(i) for i in input().split()] for _ in range(N)]

    # from random import randint
    # N, M = 10 ** 5, 10 ** 5
    # ABs = [[randint(1, 10 ** 5), randint(1, 10 ** 4)] for _ in range(10 ** 5)]

    solve(N, M, ABs)