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

n=int(input(""))
s=0
i=1
while(n>i):
    if (i==1 or i==2):
        i-=1
    i+=2
    t=0
    while(n%i==0):
        n/=i
        t+=1
    k=1
    while(t>=k):
    
        t-=k
        s+=1
        k+=1

print(s)
    

### FIXED CODE ###

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





n=int(input(""))
s=0
if(n!=1):
    

    

    t=0
    lista=prime(n)
    #print(lista)
    
    c=lista[0]
    for i in lista:
        if (c==i):
            t+=1
        else:
            k=1
            while(t>=k):
                t-=k
                s+=1
                k+=1
            t=1
            c=i


    k=1
    while(t>=k):
        t-=k
        s+=1
        k+=1
        


            
        
        
    
    


print(s)
### BUGGY CODE ###

import random
import time
t_start = time.time()

d = int(input())
c_l = list(map(int,input().split()))
s_l = [list(map(int,input().split())) for i in range(d)]


def calc_score(contest_num, last_l):
  contest_val = s_l[day][contest_num]
  point = contest_val

  temp_last_l = last_l[:]
  temp_last_l[contest_num] = day


  for i in range(26):
    point -= c_l[i] * (day - temp_last_l[i])

  return point


last_l = [-1 for i in range(26)]
ans = []
ans_p = []

point = 0
for day in range(d):
  each_point = 0
  each_contest_num = 0

  for temp_contest_num in range(26):
    temp_point = calc_score(temp_contest_num, last_l)

    if temp_point > each_point:
      each_point = temp_point
      each_contest_num = temp_contest_num

  last_l[each_contest_num] = day
#  ans.append(each_contest_num + 1)
  ans.append(each_contest_num)
  ans_p.append(each_point)
#  print(last_l)

def cp(t_l):
  ans = 0
  for day in range(d):
    contest_num = t_l[day]
    contest_num -= 1

    contest_val = s_l[day][contest_num]

    ans += contest_val
    last_l[contest_num] = day

    for i in range(26):
      ans -= c_l[i] * (day - last_l[i])

  return ans
#    print(ans)

cnt = 0
elapsed_time = time.time() - t_start
while elapsed_time < 1.95:
  cnt += 1
  change_day = random.randint(0, len(ans)-1)
  old_contest_num = ans[change_day]
  old_point = sum(ans_p)
  new_contest_num = random.randint(0, 26)

  ans[change_day] = new_contest_num
  new_point = cp(ans)
  if new_point < old_point:
    ans[change_day] = old_contest_num

  elapsed_time = time.time() - t_start

#print(cnt)
for i in ans:
  print(i+1)

#print(sum(ans_p))

### FIXED CODE ###

d = int(input())
c_l = list(map(int,input().split()))
s_l = [list(map(int,input().split())) for i in range(d)]

last_l = [-1 for i in range(26)]

def calc_score(contest_num):
  contest_val = s_l[day][contest_num]
  point = contest_val

  temp_last_l = last_l[:]
  temp_last_l[contest_num] = day

  for i in range(26):
    point -= c_l[i] * (day - temp_last_l[i])

  return point

ans = []

point = 0
for day in range(d):
  each_point = 0
  each_contest_num = 0
  for temp_contest_num in range(26):
    temp_point = calc_score(temp_contest_num)
    if temp_point > each_point:
      each_point = temp_point
      each_contest_num = temp_contest_num

  ans.append(each_contest_num + 1)

for i in ans:
  print(i)
### BUGGY CODE ###

# atcoder DPまとめ
# D_Knapsack1

def get_inputs():
    [n, w] = [int(x) for x in input().split()]
    g = []
    for _ in range(n):
        g.append([int(x) for x in input().split()])
    
    return n, w, g


if __name__ == "__main__":
    
    n, w, g = get_inputs()
    
    #### First Try
    # この方法では後半の問題でTLEになってしまう
    # 二重ループの部分で時間がかかっている
    # # dp[i][w]はi-1個目の品物を加えるか吟味した後、重さw以下で最大の価値
    # dp = [[0] * (w + 1) for _ in range(n + 1)]
    #
    # for i in range(1, n + 1):
    #     for wgt in range(w + 1):
    #         if wgt >= g[i -1][0]:
    #             dp[i][wgt] = max(dp[i - 1][wgt - g[i - 1][0]] + g[i - 1][1], dp[i - 1][wgt])
    #         else:
    #             dp[i][wgt] = dp[i - 1][wgt]
    #
    # print(max(dp[n]))

    ### Second Try
    # 動的計画法の部分で、古いiの情報は不要で一つ前の状態さえあれば解ける
    # そこに着目し、かつ不要な判定や更新を減らすために、あるiの時に、
    # 大きなwから最適値を求めるようにする

    # dp[w]は,現在評価中のiにおいて、重さwの時の最大価値の値


    ### Third Try
    # maxをやめてif文に変更

    dp = [0] * (w + 1)      # 初期値は０　範囲は0〜wまで

    for i in range(n):      # 品物0からn-1までを評価
        wt, vl = g[i]
        for j in range(w, wt - 1, -1):
            tmp = dp[j - wt] + vl
            if tmp > dp[j]:
                dp[j] = tmp

    print((dp[w]))


### FIXED CODE ###

def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = map(int, input().split())
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]
 
num, capacity = map(int, input().split())
print(calc(num,capacity))
### BUGGY CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    D = [False] * (10 ** 6 + 1)
    D[1] = True
    pairwise = True

    setwise = set()
    tmp = A[0]
    for i in range(2, int(-(-tmp ** 0.5 // 1)) + 1):
        if tmp % i == 0:
            setwise.add(i)
            while tmp % i == 0:
                tmp //= i
    if tmp != 1:
        setwise.add(tmp)

    for a in A[1:]:
        tmp = set()
        for i in range(2, int(-(-a ** 0.5 // 1)) + 1):
            if a % i == 0:
                tmp.add(i)
                if D[i]:
                    pairwise = False
                else:
                    D[i] = True
                while a % i == 0:
                    a //= i
        if a != 1:
            tmp.add(a)
            if D[a]:
                pairwise = False
            else:
                D[a] = True
        setwise &= tmp
        if setwise or pairwise:
            continue
        else:
            break
    if pairwise:
        print('pairwise coprime')
    else:
        if setwise:
            print('not coprime')
        else:
            print('setwise coprime')


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from functools import reduce
from math import gcd

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    used = [False] * (max(A) + 1)
    pairwise = True
    for a in A:
        for i in range(2, int(a ** 0.5) + 1):
            if a % i == 0:
                if used[i]:
                    pairwise = False
                else:
                    used[i] = True
                    while a % i == 0:
                        a //= i
        if a != 1:
            if used[a]:
                pairwise = False
                break
            else:
                used[a] = True


    g = reduce(gcd, A)

    if pairwise:
        print('pairwise coprime')
    else:
        if g == 1:
            print('setwise coprime')
        else:
            print('not coprime')


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

N = int(input())
ans = 10
for i in range(1,N+1):
    if(N%i==0):
        a = i
        b = int(N/i)
        F = max(len(str(a)), len(str(b)))
        ans = min(ans, F)
print(ans)

### FIXED CODE ###

N = int(input())
ans = 10
for i in range(1,int(N**0.5)+1):
    if(N%i==0):
        a = i
        b = int(N/i)
        F = max(len(str(a)), len(str(b)))
        ans = min(ans, F)
print(ans)
### BUGGY CODE ###

import itertools
from sys import exit

N = int(input())
S = input()
if N < 3:
    print(0)
    exit()

d = {'R': 0, 'G': 1, 'B': 2}
rgb = {'R', 'G', 'B'}

table = [[0] * N for _ in range(3)]
for i, s in enumerate(S):
    table[d[s]][i] = 1

for x in range(3):
    table[x] = tuple(itertools.accumulate(table[x]))

ans = 0
for k in range(2, N):
    for j in range(1, k):
        if S[j] != S[k] :
            x = (rgb - {S[j], S[k]}).pop()
            ans += table[d[x]][j - 1]
            if 2 * j - k >= 0 and S[2 * j - k] == x:
                ans -= 1
print(ans)

### FIXED CODE ###

import itertools
from sys import exit

N = int(input())
S = input()
if N < 3:
    print(0)
    exit()

d = {'R': 0, 'G': 1, 'B': 2}
rgb = {'R', 'G', 'B'}

table = [[0] * N for _ in range(3)]
for i, s in enumerate(S):
    table[d[s]][i] = 1

for x in range(3):
    table[x] = tuple(itertools.accumulate(table[x]))

ans = 0
for k in range(2, N):
    for j in range(1, k):
        if S[j] != S[k] :
            x = (rgb - {S[j], S[k]}).pop()
            ans += table[d[x]][j - 1]
            if 2 * j - k >= 0 and S[2 * j - k] == x:
                ans -= 1
print(ans)
### BUGGY CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
l.sort()
cnt = 0
for i in range(n):
    for j in range(i+1, n):
        if j == n-1:
            continue
        x = l[i] + l[j]
        cnt += bisect.bisect_left(l[j+1:], x)
print(cnt)


### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
l.sort()
cnt = 0
for i in range(n):
    for j in range(i+1, n):
        if j == n-1:
            continue
        x = l[i] + l[j]
        cnt += bisect.bisect_left(l[j+1:], x)
print(cnt)
### BUGGY CODE ###

from bisect import*
def main():
    root=[[],[]]
    def search_higher(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect(ptr[0],key)
            if i!=len(ptr[0]):ret=ptr[0][i]
            ptr=ptr[1][i]
        i=bisect(ptr[0],key)
        if i!=len(ptr[0]):ret=ptr[0][i]
        return ret
    def search_lower(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect_left(ptr[0],key)
            if i!=0:ret=ptr[0][i-1]
            ptr=ptr[1][i]
        i=bisect_left(ptr[0],key)
        if i!=0:ret=ptr[0][i-1]
        return ret
    def insert_rec(ptr,key):
        b_size=576
        if not ptr[1]:
            insort(ptr[0],key)
            if len(ptr[0])==b_size*2-1:
                ret=[ptr[0][:b_size],[]]
                ptr[0]=ptr[0][b_size:]
                return ret
        else:
            i=bisect(ptr[0],key)
            tmp=insert_rec(ptr[1][i],key)
            if tmp:
                ptr[0].insert(i,tmp[0].pop())
                ptr[1].insert(i,tmp)
                if len(ptr[1])==b_size*2:
                    ret=[ptr[0][:b_size],ptr[1][:b_size]]
                    ptr[0],ptr[1]=ptr[0][b_size:],ptr[1][b_size:]
                    return ret
    def insert(key):
        tmp=insert_rec(root,key)
        if tmp:root[0],root[1]=[tmp[0].pop()],[tmp,root]
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    insert(0)
    insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(v)-v)*(v-search_lower(v))*i
        insert(v)
    print(c)
main()

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

n=int(input())
aa=list(map(int,input().split()))
aa.append(0)
aaa=tuple(aa)
a=list(aaa)
x=[0]*(n+1)
for i in range(n-1):
    if a[i]<0:
        a[i]=-1*a[i]
        a[i+1]=-1*a[i+1]
        x[i+1]=max(sum(a),x[i])
b=list(aaa)
y=[0]*(n+1)
for i in range(n,0,-1):
    if b[i]<0:
        b[i]=-1*b[i]
        b[i-1]=-1*b[i-1]
        y[i+1]=max(sum(b),y[i])

print(max(max(x),max(y),sum(aa)))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
c=0
for i in range(n):
    if a[i]<0:
        c+=1
        a[i]=-1*a[i]
aa=list(map(abs,a))
if c%2==0:
    print(sum(aa))
else:
    print(sum(aa)-2*min(aa))
### BUGGY CODE ###

import sys
H, W, M = map(int, input().split())
hsum = [0 for i in range(H)]
wsum = [0 for i in range(W)]
s = set()
for i in range(M):
    h, w = map(int, input().split())
    h, w = h-1, w-1
    s.add((h, w))
    hsum[h] += 1
    wsum[w] += 1

hmax = max(hsum)
wmax = max(wsum)

for i in range(H):
    for j in range(W):
        if hsum[i] == hmax and wsum[j] == wmax and (i, j) not in s:
            print(hmax + wmax)
            sys.exit()
print(hmax+wmax-1)

### FIXED CODE ###

import sys
from itertools import product
H, W, M = map(int, input().split())
hsum = [0 for i in range(H)]
wsum = [0 for i in range(W)]
s = set()
for i in range(M):
    h, w = map(int, input().split())
    h, w = h-1, w-1
    s.add((h, w))
    hsum[h] += 1
    wsum[w] += 1

hmax = max(hsum)
wmax = max(wsum)

hmax_index = []
for i in range(H):
    if hsum[i] == hmax:
        hmax_index.append(i)
wmax_index = []
for i in range(W):
    if wsum[i] == wmax:
        wmax_index.append(i)

for x in hmax_index:
    for y in wmax_index:
        if (x, y) not in s:
            print(hmax+wmax)
            sys.exit()
print(hmax+wmax-1)
### BUGGY CODE ###

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

result = 1

for e in A:
    result *= e

if result > 10**18:
    print(-1)
else:
    print(result)

### FIXED CODE ###

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

if A.count(0) != 0:
    print(0)
else:
    result = 1
    for e in A:
        result *= e
        if result > 10**18:
            break

    if result > 10**18:
        print(-1)
    else:
        print(result)
### BUGGY CODE ###

"""
dp[与えたダメージ] = 使用した魔力
"""
h, n = map(int, input().split())
attacks = []
INF = 10000000000000
dp = [INF for _ in range(h + 1)]
dp[0] = 0
for i in range(n):
    a, b = map(int, input().split())
    attacks.append([a, b])
for i in range(h):
    for j in range(n):
        dp[min(h,i + attacks[j][0])] = min(dp[min(h, i + attacks[j][0])], dp[i] + attacks[j][1])
print(dp[h])


### FIXED CODE ###

"""
dp[与えたダメージ] = 使用した魔力
"""
h, n = map(int, input().split())
attacks = []
INF = 10000000000000
dp = [INF for _ in range(h + 1)]
dp[0] = 0
for i in range(n):
    a, b = map(int, input().split())
    attacks.append([a, b])
    
for i in range(h):
    for j in range(n):
        dp[min(h,i + attacks[j][0])] = min(dp[min(h, i + attacks[j][0])], dp[i] + attacks[j][1])
print(dp[h])
### BUGGY CODE ###

F=lambda X:pow(X,M-2,M);M=10**9+7;H,W,A,B=map(int,input().split());Z=C=1
for I in range(W-1-B):Z=C=C*(W+H-B-2-I)*F(I+1)%M
for I in range(1,H-A):C=C*(B-1+I)*(H-I)*F(I)*F(W+H-B-1-I)%M;Z=(Z+C)%M
print(Z)

### FIXED CODE ###

F=lambda X:pow(X,M-2,M);M=10**9+7;H,W,A,B=map(int,input().split());Z=C=1
for I in range(min(W-1-B,H-1)):Z=C=C*(W+H-B-2-I)*F(I+1)%M
for I in range(1,H-A):C=C*(B-1+I)*F(I)*(H-I)*F(W+H-B-1-I)%M;Z=(Z+C)%M
print(Z)
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(N)]
word_list=[]
for w in S:
  sort_word=''.join(sorted(w))
  word_list.append(sort_word)
word_list.sort()

import itertools
word_set=set(word_list)
total_counts=[]
for word in word_set:
  num = len(list(itertools.combinations(range(word_list.count(word)),2)))
  total_counts.append(num)
  
print(sum(total_counts))

### FIXED CODE ###

N = int(input())
S = [input() for i in range(N)]

list = {}
for i in S:
  i=''.join(sorted(i))
  if i in list:
    list[i] = list[i] + 1
  else:
    list[i] = 1

count = 0
for i in list.values():
  n = i - 1
  count = count + int(((n * (n + 1)) / 2))
  
print(count)
### BUGGY CODE ###

def is_unq(seq):
    return len(seq) == len(set(seq))

from itertools import combinations as cmb
n = int(input())
S = input()
Sli = list(S)
ans_s = [[] for _ in range(1,n+1)]
ans = 0
for x in range(n):
    lis = list(cmb(Sli,x+1))
    ans_s[x] += lis
    for y in range(len(ans_s[x])):
        flag = 0
        if is_unq(ans_s[x][y]) == True:
            ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
d = {}
mod = 10**9 + 7
for key in S:
    if key in d:
        d[key] += 1
    else:
        d[key] = 1
ans = 1
for x in d.values():
    ans *= x+1
print(ans % mod -1)
### BUGGY CODE ###

from collections import deque


h,w=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
s=[list(input()) for _ in range(h)]


for y in range(h):
    for x in range(w):
        if s[y][x]=='.':
            s[y][x]=10000000


s[c[0]-1][c[1]-1]=0
que=deque([[c[0]-1,c[1]-1]])
while que:
    y,x=que.popleft()
    for i,j in [(1,0),(0,1),(-1,0),(0,-1),(2,2),(2,1),(2,0),(2,-1),(2,-2),(1,2),(1,1),(1,-1),(1,-2),(0,2),(0,-2),(-1,2),(-1,1),(-1,-1),(-1,-2),(-2,2),(-2,1),(-2,0),(-2,-1),(-2,-2)]:
        if 0<=y+i<h and 0<=x+j<w:
            nexty,nextx=y+i,x+j
            dist=s[nexty][nextx]
            if dist!='#':
                if i*i+j*j==1:
                    if dist>s[y][x]:
                        s[nexty][nextx]=s[y][x]
                        que.append([nexty,nextx])
                elif dist>s[y][x]+1:
                    s[nexty][nextx]=s[y][x]+1
                    que.append([nexty,nextx])

if s[d[0]-1][d[1]-1]==10000000:
    print(-1)
else:
    print(s[d[0]-1][d[1]-1])


### FIXED CODE ###

from collections import deque
from sys import stdin

def bfs():
    readline=stdin.readline
    h,w=map(int,readline().split())
    sy,sx=map(int,readline().split())
    gy,gx=map(int,readline().split())
    sy-=1;sx-=1;gy-=1;gx-=1
    s=[list(readline()) for _ in range(h)]
    dict={".":10000000,"#":-1}
    s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]
    s[sy][sx]=0
    que=deque([[sy,sx]])
    temp=[i for i in range(-2,3)]
    while que:
        y,x=que.popleft()
        s1=s[y][x]
        for i in temp:
            nexty=y+i
            if 0<=nexty<h:
                s2=s[nexty]
                for j in temp:
                    nextx=x+j
                    if 0<=nextx<w and s2[nextx]>=0:
                        dist=s2[nextx]
                        if i*i+j*j<=1 and dist>s1:
                            s[nexty][nextx]=s1
                            que.appendleft([nexty,nextx])
                        elif dist>s1+1:
                            s[nexty][nextx]=s1+1
                            que.append([nexty,nextx])

    if s[gy][gx]==10000000:
        print(-1)
    else:
        print(s[gy][gx])
bfs()
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1,k+1):
            ans += gcd(a,b,c)
print(ans)

### FIXED CODE ###

import math


k = int(input())
ans = 0
dic = {}
for a in range(1, k+1):
    for b in range(1, k+1):
        tmp = math.gcd(a,b)
        for c in range(1,k+1):
            ans += math.gcd(tmp, c)
print(ans)
### BUGGY CODE ###

N = int(input())
cnt = 1
while cnt <= 9:
    s = N/cnt
    if 1 <= s <= 9 and s == type(int):
        print('Yes')
        cnt += 1
else:
    print('No')


### FIXED CODE ###

N = int(input())
for i in range(1,9 + 1):
    for j in range(1,9 +1):
        if i * j == N:
            print('Yes')
            exit()
print('No')
### BUGGY CODE ###

import sys
input = sys.stdin.readline

a, v = map(int,input().split())
b, w = map(int,input().split())
t = int(input())
for i in range(t):
    a = a + v 
    b = b + w 
if a >= b :
    print("YES")
else:
    print("NO")

### FIXED CODE ###


a, v = map(int,input().split())
b, w = map(int,input().split())
t = int(input())

if a > b:
    v = -v
    if w > 0:
        w = -w
if a < b and  w < 0:
    w = -w



A = t * v + a
B = t * w + b

if A > B:
    if  a < b:
        print("YES")
    else:
        print("NO")
elif A == B:
    print("YES")
elif A < B :
    if a < b:
        print("NO")
    else:
        print("YES")
### BUGGY CODE ###

def make_divisors(n: int):
    cnt = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1

    return cnt
res = 0
for i in range(int(input())):
    res += make_divisors(i+1) * (i+1)
print(res)

### FIXED CODE ###

ans = 0
N = int(input())
for i in range(1,N+1):
    for j in range(i,N+1,i):
        ans += j
print(ans)
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().split())
edges = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
 
q = int(input())
vv = [None] * q
dd = [None] * q
cc = [None] * q
dp = np.array([[-1 for j in range(11)] for i in range(n)])
for i in range(q):
    vv[i], dd[i], cc[i] = map(int, input().split())
    dp[vv[i] - 1][dd[i]] = i
 
for i in reversed(range(1, 11)):
    for j in range(n):
        dp[j][i - 1] = max(dp[j][i - 1], dp[j][i])
    for u, v in edges:
        dp[u][i - 1] = max(dp[u][i - 1], dp[v][i])
        dp[v][i - 1] = max(dp[v][i - 1], dp[u][i])
 
for i in range(n):
    if dp[i][0] == -1:
        print('0')
    else:
        print(cc[dp[i][0]])

### FIXED CODE ###


n, m = map(int, input().split())
edges = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]

q = int(input())
vv = [None] * q
dd = [None] * q
cc = [None] * q
dp = [[-1 for j in range(11)] for i in range(n)]
for i in range(q):
    vv[i], dd[i], cc[i] = map(int, input().split())
    dp[vv[i] - 1][dd[i]] = i

for i in reversed(range(1, 11)):
    for j in range(n):
        dp[j][i - 1] = max(dp[j][i - 1], dp[j][i])
    for u, v in edges:
        dp[u][i - 1] = max(dp[u][i - 1], dp[v][i])
        dp[v][i - 1] = max(dp[v][i - 1], dp[u][i])

for i in range(n):
    if dp[i][0] == -1:
        print('0')
    else:
        print(cc[dp[i][0]])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Jul 20 20:53:54 2019

@author: ctiuser
"""

N = int(input())
A = [int(input()) for i in range(N)]

ans = [A[0]]

for i in range(1,N):
    l,r = 0, len(ans)-1
    p = (r-l)//2 + 1
    if A[i] <= ans[r]:
        ans.append(A[i])
    elif A[i] > ans[l]:
        ans[l] = A[i]
    else:
        tmp = p
        while r - l > 1:
            if A[i] > ans[p]:
                tmp = p
                r = p
                p = (r-l)//2
            else:
                l = p
                p = (r-l)//2
        ans[tmp] = A[i]
#    print(i,ans)
print(len(ans))



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Jul 20 20:53:54 2019

@author: ctiuser
"""

N = int(input())
A = [int(input()) for i in range(N)]

ans = [A[0]]

for i in range(1,N):
    l,r = 0, len(ans)-1
    p = (r-l)//2 + 1
    if A[i] <= ans[r]:
        ans.append(A[i])
    elif A[i] > ans[l]:
        ans[l] = A[i]
    else:
        tmp = r
        while r - l > 1:
            if A[i] > ans[p]:
                tmp = p
                r = p
                p = (r-l)//2 + l
            else:
                l = p
                p = (r-l)//2 + l
        ans[tmp] = A[i]
#    print(i,ans)
print(len(ans))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import heapq

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

dict = {}
for i in range(n):
    ta, tb = map(int, input().split())
    #後でheapqから最大値を取り出したいので-1倍して追加
    if dict.get(ta) == None:
        dict[ta] = []
        dict[ta].append(tb * -1) #新しいAiを追加
    else:
        dict[ta].append(tb * -1) #既存のAiにBiを追加
#print(dict)

cand = []
ans = 0
for i in range(1, m+1):
    #１　要素の追加
    if dict.get(i) == None:
        pass
    else:
        add = dict[i]
        cand.extend(add)
        heapq.heapify(cand) #ヒープ化
        #print(cand)

    #２　heapから最大値を取り出す
    try:
        max_val = heapq.heappop(cand)
        #print(max_val)
        ans += max_val * (-1) #最大値に直す
    except: #heapに何も入っていない
        pass
#print("----")
print(ans)



### FIXED CODE ###

# -*- coding: utf-8 -*-

import heapq

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

work = [[] for _ in range(10**5+1)]
for i in range(n):
    ta, tb = map(int, input().split())
    work[ta].append(tb)

total = 0
cand = []

for d in range(1, m+1):
    for w in work[d]:
        #後で最大値を取り出したいので-1倍して追加
        #（複数の要素も一気にpush）
        heapq.heappush(cand, -w) 
        
    if len(cand) > 0:
        #-1倍して最大値として取得
        total += heapq.heappop(cand)*(-1) 
        
print(total)