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

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def make_adjlist_d(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


def main():
    N, M = NMI()
    edges = [NLI() for _ in range(M)]
    S, T = NMI()
    tree = make_adjlist_d(N, edges)

    tree = [set(tr) for tr in tree]

    tree2 = [[] for _ in range(N+1)]
    for i in range(1, N+1):
        gotos = tree[i]
        for goto in gotos:
            tree2[i] += tree[goto]

    tree2 = [set(tr) for tr in tree2]

    tree3 = [[] for _ in range(N+1)]
    for i in range(1, N+1):
        gotos = tree2[i]
        for goto in gotos:
            tree3[i] += tree[goto]

    tree3 = [set(tr) for tr in tree3]

    stack = deque()
    stack.append(S)
    seen = [-1] * (N+1)
    seen[S] = 0
    while stack:
        now = stack.popleft()
        now_step = seen[now]
        for goto in tree3[now]:
            if seen[goto] >= 0:
                continue

            stack.append(goto)
            seen[goto] = now_step + 1

    print(seen[T])



if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def make_adjlist_d(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


def main():
    N, M = NMI()
    edges = [NLI() for _ in range(M)]
    S, T = NMI()

    tree = [[] for _ in range(3*N+1)]
    for e in edges:
        tree[e[0]].append(e[1]+N)
        tree[e[0]+N].append(e[1]+2*N)
        tree[e[0]+2*N].append(e[1])

    stack = deque()
    stack.append(S)
    seen = [-1] * (3*N+1)
    seen[S] = 0
    while stack:
        now = stack.popleft()
        now_step = seen[now]
        for goto in tree[now]:
            if seen[goto] >= 0:
                continue

            stack.append(goto)
            seen[goto] = now_step + 1

    print(seen[T]//3)



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

N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = [float('inf')]*N
ans[0] = 0
K = min(N-1,K)
for i in range(1,K+1):
  ans[i] = abs(A[0]-A[i])

for i in range(K+1,N):
  for j in range(0,min(i,K)):
    ans[i] = min(ans[i],ans[i-j]+abs(A[i]-A[i-j]), ans[i-j-1]+abs(A[i]-A[i-j-1]))
print(ans[N-1])

### FIXED CODE ###

import numpy as np
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = np.array(A)
ans = np.array([float('inf')]*N)
ans[0] = 0
K = min(N-1,K)
for i in range(1,K+1):
  ans[i] = abs(A[0]-A[i])
for i in range(K+1,N):
  ans[i] = min(ans[i],np.min(ans[i-K:i]+np.abs(A[i]-A[i-K:i])))
print(int(ans[N-1]))
### BUGGY CODE ###

n = int( input() )
strs = []
for i in range( n ):
	strs.append( ''.join( sorted( list( input() ) ) ) )

count = 0
strs = sorted( strs )
for i in range( n ) :
	bFound = False
	for j in range( i+1, n ) :
		if strs[i] != strs[j] :
			break
		if strs[i] == strs[j] :
			count += 1
			bFound = True

print( count )

### FIXED CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

#=-------------------------------------  
n = int( input() )

dict = {}
for i in range( n ):
	sorted_input = "".join( sorted( list( input() ) ) )
	if dict.get( sorted_input ) == None:
		dict[ sorted_input ] = 1
	else :
		dict[ sorted_input ] += 1

count = 0
for eachValue in dict.values():
	if eachValue == 1 : continue
	count += cmb( eachValue, 2 )
print( count )
### BUGGY CODE ###

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

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
b=[0]*n
for i in a:
  b[i-1]+=1
print(*b, sep="\n")
### BUGGY CODE ###

import itertools
import math
import fractions
import functools
import copy
n, m = map(int, input().split())
lr = []
for i in range(m):
    l, r = map(int, input().split())
    lr.append([l,r])

result = list(range(lr[0][0],lr[0][1]+1))

for i in range(len(result)):
    for pair in lr:
        if not(pair[0] <= result[i] and pair[1] >= result[i]):
            result[i] = -1

print(len(result)-result.count(-1))



### FIXED CODE ###

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

lr = []
for i in range(m):
    l = list(map(int, input().split()))
    lr.append(l)

count = 0
minimum = 0
maxmum = 10**9
for i in range(m):
    minimum = max(minimum, lr[i][0])
    maxmum = min(maxmum, lr[i][1])

if(maxmum >= minimum):
    print(maxmum - minimum + 1)
else:
    print(0)
### BUGGY CODE ###

import heapq
n, k, q = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)
a = [0] + a + [0]
ans = 10**30
for x in b:
	removed = []
	que = []
	for i in range(n+2):
		if a[i] < x:
			if len(que) >= k:
				removed += heapq.nsmallest(len(que)-k+1, que)
			que = []
		else:
			que.append(a[i])
	if len(removed) < q:
		continue
	removed.sort()
	ans = min(ans, removed[q-1] - x)
print(ans)

### FIXED CODE ###

import sys, heapq
def input():
	return sys.stdin.readline()[:-1]

n, k, q = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)
a = [0] + a + [0]
ans = 10**30
for x in b:
	removed = []
	que = []
	for i in range(n+2):
		if a[i] < x:
			que = []
		else:
			heapq.heappush(que, a[i])
			if len(que) == k:
				removed.append(heapq.heappop(que))
	if len(removed) < q:
		continue
	removed.sort()
	ans = min(ans, removed[q-1] - x)
print(ans)
### BUGGY CODE ###

def resolve():
    ss = input()

    dp = [0] * 13
    dp[0] = 1

    mod = 10 ** 9 + 7
    mul = 1

    # 後ろから解く
    for s in ss[::-1]:
        next_dp = [0] * 13

        if s == '?':
            for num in range(10):
                for i in range(13):
                    next_dp[(num * mul + i) % 13] += dp[i]
        else:
            num = int(s)
            for i in range(13):
                next_dp[(num * mul + i) % 13] += dp[i]

        mul *= 10
        mul %= 13
        dp = next_dp

    print(dp[5] % mod)
    
resolve()

### FIXED CODE ###

def resolve():
    ss = input()

    dp = [0] * 13
    dp[0] = 1

    mod = 10 ** 9 + 7
    mul = 1

    # 後ろから解く
    for s in ss[::-1]:
        next_dp = [0] * 13

        if s == '?':
            for num in range(10):
                for i in range(13):
                    next_dp[(num * mul + i) % 13] += dp[i]
                    next_dp[(num * mul + i) % 13] %= mod
        else:
            num = int(s)
            for i in range(13):
                next_dp[(num * mul + i) % 13] += dp[i]
                next_dp[(num * mul + i) % 13] %= mod

        mul *= 10
        mul %= 13
        dp = next_dp

    print(dp[5])
    
resolve()
### BUGGY CODE ###

import sys
from collections import defaultdict
from collections import deque
input = sys.stdin.readline

new_cards = defaultdict(int)
n, m = map(int, input().split())
A = deque(sorted(list(map(int, input().split()))))

for i in range(m):
    b, c = map(int, input().split())
    new_cards[c] += b

for card in sorted(new_cards.keys(), reverse=True):
    count = new_cards[card]
    for i in range(count):
        if A[0] < card:
            A.append(card)
            A.popleft()

print(sum(A))


### FIXED CODE ###

import sys
from collections import defaultdict
from collections import deque
input = sys.stdin.readline

new_cards = defaultdict(int)
n, m = map(int, input().split())
A = deque(sorted(list(map(int, input().split()))))

for i in range(m):
    b, c = map(int, input().split())
    new_cards[c] += b

for card, count in sorted(new_cards.items(), reverse=True):
    for i in range(count):
        if A[0] < card:
            A.append(card)
            A.popleft()
        else:
            print(sum(A))
            exit()

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

import numpy as np

N = int(input()) 
a = np.zeros((100, 100, 100), dtype=np.int32)
 
 
for i in range(1, 100):
    for j in range(1, 100):
        for k in range(1, 100):
            n = int( ((i+j) * (j+k)) + i*i + k*k)
            a[i,j,k] = n
 
            if n > 1001:
                break
for i in range(N):
    print(np.count_nonzero(a == (i+1)))
 

### FIXED CODE ###

import sys
import numpy as np

N = int(input())

o = [0] * (N+1)
for i in range(1, 100):
    for j in range(1, 100):
        for k in range(1, 100):
            n = int( ((i+j) * (j+k)) + i*i + k*k)
            if n < (N+1):
                o[n] += 1
            if n > 10001:
                break

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

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort()
    num_tmp = [0]*(A[-1]+1)

    for a in A:
        num_tmp[a] += 1
        if num_tmp[a] == 1:
            for i in range(2*a,max(A)+1,a):
                num_tmp[i] = 2

    print(num_tmp.count(1))
    
main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort()
    MAX = A[-1]+1
    num_tmp = [0]*MAX

    for a in A:
        num_tmp[a] += 1
        if num_tmp[a] == 1:
            for i in range(2*a,MAX,a):
                num_tmp[i] = 2

    print(num_tmp.count(1))
    
main()
### BUGGY CODE ###

import bisect
n = int(input())
*L, = map(int, input().split())
L.sort()
cnt = 0
for i in range(n-2):
    a = L[i]
    for j in range(i+1, n-1):
        b = L[j]
        l = max(j+1, bisect.bisect_left(L, b-a))
        r = bisect.bisect_left(L, b+a)
        cnt += r-l
print(cnt)


### FIXED CODE ###

import bisect
N=int(input())
L=list(map(int,input().split()))
L.sort()
count=0
for i in range(N-2):
    for j in range(i+1,N-1):
        a=L[i]
        b=L[j]
        count+=bisect.bisect_left(L,a+b)-(j+1)
print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import math
 
def INT(): return int(input())
def MAPINT(): return map(int, input().split())
def LMAPINT(): return list(map(int, input().split()))
def STR(): return input()
def MAPSTR(): return map(str, input().split())
def LMAPSTR(): return list(map(str, input().split()))
 
f_inf = float('inf')
 
n = INT()
a = sorted(LMAPINT())

ans = [0] * (max(a) + 1)
for i in range(n):
  # 重複
  if ans[a[i]] != 0:
    ans[a[i]] = 2
    continue
  for j in range(a[i], max(a)+1, a[i]):
    ans[j] += 1

count = 0
for x in a:
  if ans[x] == 1:
    count += 1
print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
xs = [0] * (max(a) + 1)
 
for v in a:
    if xs[v] == 0:
        for j in range(v, len(xs), v):
            xs[j] += 1
    else:
        xs[v] += 1
print(len(list(filter(lambda v: xs[v] == 1, a))))
### BUGGY CODE ###

def main():
  n = int(input())
  flag = 0
  while n > 0:
      if n % 10 == 7:
          flag += 1
          n /= 10
  if flag > 0:
      print('Yes')
  else:
      print('No')
main()

### FIXED CODE ###

def main():
  n = input()
  
  if n[0] == '7' or n[1] == '7' or n[2] == '7':
      print('Yes')
  else:
      print('No')
main()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    def com(com_n, com_r):
        return fac[com_n] * inv[com_r] * inv[com_n - com_r] % md

    n, k = MI()
    aa = LI()
    # combinationの準備
    md = 10 ** 9 + 7
    n_max = n + 3
    fac = [1] * (n_max + 1)
    inv = [1] * (n_max + 1)
    for i in range(2, n_max + 1): fac[i] = fac[i - 1] * i % md
    inv[n_max] = pow(fac[n_max], md - 2, md)
    for i in range(n_max - 1, 1, -1): inv[i] = inv[i + 1] * (i + 1) % md

    dp = [0] * (n + 1)
    dp[0] = 1
    for a in aa:
        for j in range(n, -1, -1):
            pre = dp[j]
            if pre == 0: continue
            dp[j] = 0
            for dj in range(a + 1):
                nj = j + dj
                if nj > n or a - dj < 0 or n - j < dj: break
                dp[nj] += pre * com(n - j, dj) * com(n - dj, a - dj) % md
        # print(dp)
    print(dp[n] % md)

main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    def com(com_n, com_r):
        return fac[com_n] * inv[com_r] * inv[com_n - com_r] % md

    n, k = MI()
    aa = LI()
    # combinationの準備
    md = 10 ** 9 + 7
    n_max = n + 3
    fac = [1] * (n_max + 1)
    inv = [1] * (n_max + 1)
    for i in range(2, n_max + 1): fac[i] = fac[i - 1] * i % md
    inv[n_max] = pow(fac[n_max], md - 2, md)
    for i in range(n_max - 1, 1, -1): inv[i] = inv[i + 1] * (i + 1) % md

    dp = [0] * (n + 1)
    dp[0] = 1
    for a in aa:
        for j in range(n, -1, -1):
            pre = dp[j]
            if pre == 0: continue
            dp[j] = 0
            for dj in range(a + 1):
                nj = j + dj
                if nj > n or a - dj < 0 or n - j < dj: break
                dp[nj] += pre * com(n - j, dj) * com(n - dj, a - dj)
                dp[nj] %= md
        # print(dp)
    print(dp[n])

main()
### BUGGY CODE ###

N, C = [int(i) for i in input().split(" ")]
x = [0]
v = [0]
for i in range(N):
    t = [int(i) for i in input().split(" ")]
    x.append(t[0])
    v.append(t[1])
x.append(C)
v.append(0)
    

right_cal = [0 for i in range(N + 2)]
for i in range(1, N + 1):
    right_cal[i] = (v[i] + right_cal[i - 1] - x[i] + x[i - 1])
    
left_cal = [0 for i in range(N + 2)]
for i in range(N, 0, -1):
    left_cal[i] = (v[i] + left_cal[i + 1] - x[i + 1] + x[i])

ans = max(max(right_cal), max(left_cal))
for i in range(N + 2):
    for j in range(N + 2):
        if i >= j:
            continue
        ans = max(ans, right_cal[i] + left_cal[j] - x[i], right_cal[i] + left_cal[j] - C + x[j])
    
# print(right_cal)
# print(left_cal)
print(ans)

### FIXED CODE ###

x = [0 for i in range(100001)]
v = [0 for i in range(100001)]
v_sum_right = [0 for i in range(100001)]
v_sum_left = [0 for i in range(100001)]
g = [[0, 0] for i in range(100001)]
g2= [0 for i in range(100001)]
N = 0
C = 0
i = 0
ans = 0
t = 0

N, C = [int(i) for i in input().split(" ")]
for i in range(N):
    x[i], v[i] = [int(i) for i in input().split(" ")]


v_sum_right[0] = v[0]
for i in range(1, N):
    v_sum_right[i] = v_sum_right[i - 1] + v[i]

v_sum_left[N] = 0
for i in range(N - 1, -1, -1):
    v_sum_left[i] = v_sum_left[i + 1] + v[i]


# // g計算
g[0][0] = 0
g[0][1] = 0
g2[0] = 0
for i in range(1, N + 1):
    g[i][0] = max(g[i - 1][0], v_sum_right[i - 1] - x[i - 1])
    g2[i] = max(g2[i - 1], v_sum_right[i - 1] - 2 * x[i - 1])
    if g[i - 1][0] == g[i][0]:
        g[i][1] = g[i - 1][1]
    else:
        g[i][1] = x[i - 1]
    
# // 探査
ans = v_sum_left[0] - C + x[0]
for i in range(1, N):
    ans = max(ans, v_sum_left[i] + g[i][0] - 2 * (C +- x[i]), v_sum_left[i] - C + x[i] + g2[i])
ans = max(ans, g[N][0])

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

# ABC143 D Triangles

n = int(input())
l_list = [int(x) for x in input().split()]

l_list.sort()
ans = 0

# (i < j < k) -> (_a < _b < _c)
for i in range(n-2):
    _a = l_list[i]
    for j in range(i+1,n-1):
        _b = l_list[j]
        _tmp = _a + _b
        for k in range(j+1,n):
            _c = l_list[k]
            if _c < _tmp:
                ans += 1
            else:
                break

print(ans)

### FIXED CODE ###

# ABC143 D Triangles

import bisect

n = int(input())
l_list = [int(x) for x in input().split()]

l_list.sort()
ans = 0

for i in range(n-2):
    _a = l_list[i]
    for j in range(i+1,n-1):
        _b = l_list[j]
        _tmp = bisect.bisect_left(l_list, _a+_b)
        if j < _tmp:
            ans += _tmp - j - 1

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

K = int(input())
A = tuple(map(int, input().split()))

l, r = 1, 10 ** 18
while r - l > 1:
    m = (l + r) // 2
    M = m
    for a in A:
        M = (M // a) * a

    if M <= 2:
        l = m
    else:
        r = m
ans_max = l

l, r = 1, 10 ** 18
while r - l > 1:
    m = (l + r) // 2
    M = m
    for a in A:
        M = (M // a) * a

    if M >= 2:
        r = m
    else:
        l = m
ans_min = r

if ans_min > ans_max:
    print(-1)
else:
    print(ans_min, ans_max)


### FIXED CODE ###

K = int(input())
A = tuple(map(int, input().split()))

l, r = 1, 10 ** 18
while r - l > 1:
    m = (l + r) // 2
    M = m
    for a in A:
        M = (M // a) * a

    if M <= 2:
        l = m
    else:
        r = m
ans_max = l

l, r = 1, 10 ** 18
while r - l > 1:
    m = (l + r) // 2
    M = m
    for a in A:
        M = (M // a) * a

    if M >= 2:
        r = m
    else:
        l = m
ans_min = r

if ans_min > ans_max:
    print(-1)
else:
    print(ans_min, ans_max)
### BUGGY CODE ###

X = input()
while 'ST' in X:
    X = X.replace('ST','')
print(len(X))

### FIXED CODE ###

X = input()
st = []
for s in X:
    if s == 'S': st.append(s)
    if s == 'T':
        if (not st) or st[-1] == 'T': st.append(s)
        if st[-1] == 'S': st.pop()
print(len(st))
### BUGGY CODE ###

class Node:
    def __init__(self):
        self.num = None
        self.parent = None
        self.children = list()
        self.added = 0
        self.count = None
    def __repr__(self):
        return f'Node({self.num})'
    def calc_count(self):
        if self.parent is None:
            self.count = self.added
            return
        elif self.parent.count is None:
            self.parent.calc_count()
        self.count = self.parent.count + self.added

(n,q),*abpx = [list(map(int, s.split())) for s in open(0)]

ab,px = abpx[:n-1],abpx[n-1:]

from collections import defaultdict,deque
d = defaultdict(Node)

oab = ab
resid = []
ab = []
parents = {1}

while oab:
    for a,b in oab:
        if a in parents:
            ab.append((a,b))
            parents.add(b)
        elif b in parents:
            ab.append((b,a))
            parents.add(a)
        else:
            resid.append((a,b))
    oab = resid

for a,b in ab:
#     d[a].num = a
#     d[b].num = b
    d[b].parent = d[a]
    d[a].children.append(d[b])

for p,x in px:
    d[p].added += x

dq = deque([d[1]])

while dq:
    cur = dq.popleft()
    if cur.children:
        dq.extend(cur.children)
    cur.calc_count()

print(*list(d[i].count for i in range(1,n+1)))

### FIXED CODE ###

(n,q),*abpx = [list(map(int, s.split())) for s in open(0)]
ab,px = abpx[:n-1],abpx[n-1:]

from collections import defaultdict, deque
add = defaultdict(int)

for p,x in px:
    add[p] += x

links = defaultdict(set)

for a,b in ab:
    links[a].add(b)
    links[b].add(a)

passed = set()

dq = deque()
dq.append((0,1))

ans = {}

while dq:
    to_add, cur = dq.popleft()
    tmp = to_add + add[cur]
    ans[cur] = tmp
    for nx in links[cur]:
        links[nx].remove(cur)
        dq.append((tmp, nx))

print(*(ans[i] for i in range(1,n+1)))
### BUGGY CODE ###

input()
s = input()

def f(i):
  w = s[0:i]
  e = s[i:]

  wl = filter(lambda c: c == 'W', w)
  el = filter(lambda e: e == 'E', e)

  return len(list(wl) + list(el))

l = map(f, range(len(s)))

print(min(list(l)))

### FIXED CODE ###

input()
s = input()

l = 0
r = s[1:].count('E')
x = l + r

for i in range(1, len(s)):
  if s[i - 1] == 'W':
    l += 1

  if s[i] == 'E':
    r -= 1
  x = min(x, l + r)

print(x)
### BUGGY CODE ###

from collections import defaultdict
n,p = map(int, input().split())
s = input()

if p==2 or p==5:
    res = 0
    for i in range(n-1,-1,-1):
        if int(s[i])%p==0:
            res += i+1
    print(res)
    exit()

u = defaultdict(int)
u[0] = 1
for i in range(n):
    d = int(s[i:])
    u[d%p] += 1

res = 0
for v in u.values():
    res += v*(v-1)//2

print(res)

### FIXED CODE ###

from collections import defaultdict
n,p = map(int, input().split())
s = input()

if p==2 or p==5:
    res = 0
    for i in range(n-1,-1,-1):
        if int(s[i])%p==0:
            res += i+1
    print(res)
    exit()

u = defaultdict(int)
u[0] = 1
f = 1
d = 0
for i in range(n-1,-1,-1):
    d = (d + int(s[i])*f)%p
    f = (f*10)%p
    u[d%p] += 1

res = 0
for v in u.values():
    res += v*(v-1)//2

print(res)
### BUGGY CODE ###

from bisect import bisect_right as br
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort()
A=[a for a,b in AB]
B=[b for a,b in AB]
works=[]
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  #worksにlatest日以内に報酬を貰える仕事を追加する
  if not A or A[0]>latest:
    pass
  else:
    for _ in range(br(A,latest)):
      A.pop(0)
      works.insert(br(works,B[0]),B[0])
      B.pop(0)
  if not works:
    continue
  ans+=works.pop(-1)

print(ans)


### FIXED CODE ###

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

AB.sort(reverse=True)
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  while AB and AB[-1][0]<=latest:
    a,b=AB.pop()
    heapq.heappush(works,-b)
  if not works:
    continue
  ans-=heapq.heappop(works)

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

# https://atcoder.jp/contests/abc077/tasks/arc084_a
# C - Snuke Festival

N = int(input().split()[0])
a_list = sorted(list(map(int, input().split())))
b_list = sorted(list(map(int, input().split())))
c_list = sorted(list(map(int, input().split())))

comb_n = 0

for i in range(N):  # 10 ** 5
    b = b_list[i]
    c_n = len([c for c in c_list if c > b])  # 10 ** 5
    a_n = len([a for a in a_list if a < b])  # 10 ** 5
    comb_n += a_n * c_n

ans = comb_n
print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/abc077/tasks/arc084_a
# C - Snuke Festival
import bisect

N = int(input().split()[0])
a_list = sorted(list(map(int, input().split())))
b_list = sorted(list(map(int, input().split())))
c_list = sorted(list(map(int, input().split())))

comb_n = 0
comb_n_list = []

# 自分より大きい個数
start_c_index = 0
start_a_index = 0

for i in range(N):  # 10 ** 5
    b = b_list[i]
    a_n = bisect.bisect_left(a_list, b)
    c_n = N - bisect.bisect_right(c_list, b)
    comb_n += a_n * c_n
ans = comb_n
print(ans)
### BUGGY CODE ###

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

mod = 10**9+7
ans = 0
for i in range(n-1):
  ans += a[i] * sum(a[i+1:])
  ans %= mod
print(ans)

### FIXED CODE ###

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

mod = 10**9+7
nums = [0]*n
nums[0] = a[0]
for i in range(1,n): nums[i] = a[i] + nums[i-1]

ans = 0
for i in range(n-1):
  ans += a[i] * (nums[n-1]-nums[i])
  ans %= mod
print(ans)
### BUGGY CODE ###

n,m=map(int, input().split(" "))
#min=0
#max=1000000000
arr=[[0,100000000]]
for i in range(m):

    flag=1
    a,b=map(int, input().split(" "))
    for n,j in enumerate(arr):
        flag=1
        if j[0]<=a and j[1]>=b:
            del arr[n]
            #arr.remove(j)
        elif j[0]>=a and j[1]<=b:
            flag=0
            break
    if flag==1:
        arr.append([a,b])

#arr.sort(key=lambda x:x[0])
arr.sort(key=lambda x:(x[0],x[1]))
#print(arr)
#count=0
num=0
count=0
for i in range(len(arr)):
    if arr[i][0]-num>=0:
        count+=1
        num=arr[i][1]

print(count)


### FIXED CODE ###

n,m=map(int, input().split(" "))
arr=[]
for i in range(m):
    a,b=map(int, input().split(" "))

    arr.append([a,b])

#arr.sort(key=lambda x:x[0])
arr.sort(key=lambda x:(x[0],x[1]))
left=0
num=0
count=0
for i in range(len(arr)):
    if arr[i][0]==left:
        pass
    if arr[i][1]<=num:
        num=arr[i][1]
    if arr[i][0]-num>=0:
        count+=1
        num=arr[i][1]
        left=arr[i][0]
    #print(arr[i],count)
print(count)