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

import numpy as np
import bisect
N, M = map(int, input().split())
As = sorted(list(map(int, input().split())), reverse=True)
cards = np.array(As, dtype=np.int64) * -1

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

    p = bisect.bisect_right(cards, -C)
    if p >= N:
        continue

    replace = min(N - p, B)
    cards[p+replace:] = cards[p:N-replace]
    cards[p:p+replace] = -C

total = 0
for card in cards:
    total += -card
print(total)

### FIXED CODE ###

import heapq
from collections import defaultdict

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

As = map(int, input().split())
counts = defaultdict(int)
for A in As:
    counts[A] += 1
h = sorted(counts.keys())

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

    if C not in counts:
        heapq.heappush(h, C)
    counts[C] += B
    if len(h) > N:
        v = heapq.heappop(h)
        del counts[v]

total_count = 0
total = 0
for k in sorted(h, reverse=True):
    c = counts[k]
    c = min(c, N - total_count)
    total += k * c
    total_count += c
    if total_count > N:
        break
print(total)
### BUGGY CODE ###

from collections import  deque
h,w = map(int,input().split())
mp = []
for _ in range(h):
    row = list(input())
    mp.append(row)

q = deque()
dist = [[-1] * w for _ in range(h)]

for col in range(h):
    for row in range(w):
        if mp[col][row] == '#':
            q.append((col,row))
            dist[col][row] = 0
ans = 0
while q:
    now = q.popleft()
    for x,y in ((1,0), (0,1), (-1,0), (0,-1)):
        next_x = now[0] + x
        next_y = now[1] + y
        if 0 <= next_x < h and 0 <= next_y < w :
            if dist[next_x][next_y] < 0:
                q.append((next_x, next_y))
                dist[next_x][next_y] = dist[now[0]][now[1]] + 1
                ans = max(ans,dist[next_x][next_y])
print(ans)


### FIXED CODE ###

from collections import  deque
h,w = map(int,input().split())
mp = []
for _ in range(h):
    row = list(input())
    mp.append(row)

q = deque()
dist = [[-1] * w for _ in range(h)]

for col in range(h):
    for row in range(w):
        if mp[col][row] == '#':
            q.append((col,row))
            dist[col][row] = 0
ans = 0
while q:
    now_x,now_y = q.popleft()
    ans = dist[now_x][now_y]
    for x,y in ((1,0), (0,1), (-1,0), (0,-1)):
        next_x = now_x + x
        next_y = now_y + y
        if 0 <= next_x < h and 0 <= next_y < w :
            if dist[next_x][next_y] < 0:
                q.append((next_x, next_y))
                dist[next_x][next_y] = ans + 1

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

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
S = input()

res = 0
start = 0
min_length = 4
end = start+min_length
max_end = len(S)

if len(S) < 4:
  pass
else:
  while True:
    tmp_s = S[start:end]

    if int(tmp_s) % 2019 == 0:
      res += 1

    if end+1 <= max_end:
      end += 1
    elif end-(start+1) >= min_length:
      start += 1
      end = start + min_length
    else:
      break
    
print(res)

### FIXED CODE ###

s = input()[::-1]

sum_of_digits = 0

cnts = [0] * 2019

cnts[0] = 1

d = 1

for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    cnts[sum_of_digits] += 1

ans = 0
    
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2

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

import itertools
N,K = map(int,input().split())
A = list(map(int,input().split()))
for i in range(K):
    newA = [0]*N
    for j in range(N):
        newA[max(0,j-A[j])] += 1
        if j+A[j]+1 < N:
            newA[min(N-1,j+A[j]+1)] -= 1
    A = list(itertools.accumulate(newA))
for i in range(N):
    A[i] = str(A[i])
print(' '.join(A))

### FIXED CODE ###

import itertools
N,K = map(int,input().split())
A = list(map(int,input().split()))
if K >= 50:
    print(*[N]*N)
    exit()
for i in range(K):
    newA = [0]*N
    for j in range(N):
        newA[max(0,j-A[j])] += 1
        if j+A[j]+1 < N:
            newA[min(N-1,j+A[j]+1)] -= 1
    A = list(itertools.accumulate(newA))
    if A == [N]*N:
        break
print(*A)
### BUGGY CODE ###

n=int(input())
graph=[[] for i in range(n)]
node=[[-1]*n for i in range(n)]
color=[0]*n
visited=[False]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    graph[a-1].append(b-1);node[a-1][b-1]=c%2
    graph[b-1].append(a-1);node[b-1][a-1]=c%2
search=[[0,i] for i in graph[0]]
while search!=[]:
  a=search.pop(0)
  if visited[a[1]]==True:continue
  search=search+[[a[1],i] for i in graph[a[1]]]
  color[a[1]]=color[a[0]]^node[a[0]][a[1]]
  visited[a[1]]=True
for i in color:
  print(i)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n=int(input())
graph=[[] for i in range(n)]
color=[-1]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    graph[a-1].append([b-1,c%2])
    graph[b-1].append([a-1,c%2])
def coloring(pre,c):
  color[pre]=c
  for i,j in graph[pre]:
    if color[i]<0:
      coloring(i,color[pre]^j)
coloring(0,1)
for i in color:
  print(i)
### BUGGY CODE ###

import itertools
n = int(input())
src = [''.join(sorted(input())) for _ in range(n)]
dic = {}
for s in src:
    # 辞書にキーが存在しなければキー追加
    if s not in dic:
        dic[s] = 0
    else:
        dic[s] += 1
count = 0
# 辞書から値だけ取り出す
for d in dic.values():
    count += len(list(itertools.combinations(range(d+1), 2)))
print(count)

### FIXED CODE ###

from math import factorial
n = int(input())
src = [''.join(sorted(input())) for _ in range(n)]
dic = {}
for s in src:
    # 辞書にキーが存在しなければキー追加
    if s not in dic:
        dic[s] = 1
    else:
        dic[s] += 1
count = 0
# 辞書から値だけ取り出す
for d in dic.values():
    # dまでの値の組み合わせを合計する
    if d > 2:
        count += factorial(d) // 2 // factorial(d - 2)
    elif d == 2:
        count += 1
print(count)
### BUGGY CODE ###

from collections import Counter
from math import factorial

def combinations_count(n, r):
  if n-r < 0:
    return 0
  else:
    return factorial(n) // (factorial(n-r) * factorial(r))

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

c = Counter(a)
counts = c.most_common()
d = {}
for each in counts:
  d[each[0]] = combinations_count(each[1], 2)
  
for each in a:
  tmp = sum(d.values()) - d[each]
  tmp += combinations_count(c[each]-1, 2)
  print(tmp)

### FIXED CODE ###

from collections import Counter

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

d = Counter(a)

dict1 = {}
dict2 = {}
for key in d:
  m = d[key]
  if m == 1:
    dict1[key] = 0
    dict2[key] = 0
  elif m == 2:
    dict1[key] = 1
    dict2[key] = 0
  else:
    dict1[key] = m*(m-1)//2
    dict2[key] = (m-1)*(m-2)//2

s = sum(dict1.values())
for each in a:
  tmp = s - dict1[each] + dict2[each]
  print(tmp)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
def dfs(v):
    global gone
    dist = [-1] * (n+1)
    stack = [v]
    dist[v] = 0
    gone[v] = True
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in graph[v]:
            if dist[w] >= 0:
                continue
            dist[w] = dw
            gone[w] = True
            stack.append(w)

n,m = map(int,input().split())
exist = [False for i in range(n+1)]
gone = [False for i in range(n+1)]
graph = [[] for _ in range(n+1)]
for i in range(m):
    x,y,z = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
    exist[x] = True
    exist[y] = True
ans = 0

for i in range(1,n+1):
    if exist[i] == True:
        if gone[i] == False:
            dfs(i)
            ans += 1
    else:
        ans += 1

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
def dfs(v):
    global gone
    stack = [v]
    gone[v] = True
    while stack:
        v = stack.pop()
        for w in graph[v]:
            if gone[w] == False:
                stack.append(w)
            gone[w] = True

n,m = map(int,input().split())
exist = [False for i in range(n+1)]
gone = [False for i in range(n+1)]
graph = [[] for _ in range(n+1)]
for i in range(m):
    x,y,z = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
    exist[x] = True
    exist[y] = True
ans = 0

for i in range(1,n+1):
    if exist[i] == True:
        if gone[i] == False:
            dfs(i)
            ans += 1
    else:
        ans += 1

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

n = int(input())
a = list(input().split())
q = int(input())
for i in range(q):
    b, c = input().split()
    replace_a = [i.replace(b, c) if i == b else i for i in a]
    print(sum(map(int, replace_a)))
    a = replace_a


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
sum_a = sum(a)
count_a = Counter(a)
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    tmp = count_a[b]
    new = {c : tmp}
    count_a.update(new)
    del count_a[b]
    sum_a = sum_a - b * tmp + c * tmp
    print(sum_a)
### BUGGY CODE ###

L, R = map(int, input().split())

R = min(R, L+4038)

ans = 2018

for i in range(L, R+1):
    for j in range(i+1, R+1):
        x = (i*j) % 2019
        ans = min(ans, x)

print(ans)

### FIXED CODE ###

L, R = map(int, input().split())

if R - L >= 2019:
    ans = 0
else:
    l, r = L % 2019, R % 2019
    ans = 2018 ** 2
    for i in range(l, r+1):
        for j in range(i+1, r+1):
            x = (i*j) % 2019
            ans = min(ans, x)

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

n=int(input())
a=sorted(list(map(int,input().split())))[::-1]
ans=0
d={}
for i in a:
  if d.get(i):d[i]+=1
  else:d[i]=1
for i in range(n):
  if d[a[i]]!=1:continue
  for j in range(i+1,n):
    if a[i]%a[j]==0:break
  else:ans+=1
print(ans)

### FIXED CODE ###

def sieve(n=10**6):
  p=[-1]*(n+1)
  for i in a:
    if p[i]==-1:
      p[i]=1
      for j in range(2*i,n+1,i):p[j]=0
    elif p[i]==1:
      p[i]=0
  return p
n=int(input())
a=sorted(list(map(int,input().split())))
p=sieve()
ans=0
for i in a:
  ans+=p[i]
print(ans)
### BUGGY CODE ###

"""from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd"""

N,P=map(int,input().split())
S=input()
dp=[[0 for i in range(P)] for n in range(N)]
#visited=set()
for n,s in enumerate(S):
    s=int(s)
    for i in range(P):
        A=(i*10+s)%P
        dp[n][A]+=dp[n-1][i]
    dp[n][s%P]+=1


count=0
for i in dp:
    count+=i[0]
print(count)


### FIXED CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

N,P=map(int,input().split())
S=input()

if P in [2,5]:
    count=0
    for i in range(N):
        if int(S[i])%P==0:
            count+=i+1
    print(count)
    exit()
S=list(S)
S.reverse()
nlst=[0,int(S[0])%P]
for i in range(1,N):
    nlst.append((nlst[i]+int(S[i])*pow(10,i,P))%P)

count=0
for i,n in Counter(nlst).most_common():
    count+=n*(n-1)//2

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

def resolve():
    import numpy as np
    import itertools
    import copy

    H, W, K = map(int, input().split())
    table = []
    for _ in range(H):
        s = input()
        inte = []
        for i in range(W):
            if s[i] == '.':
                inte.append(0)
            else:
                inte.append(1)
        table.append(np.array(inte))

    ans = 0
    table = np.asarray(table)
    q_w = list(range(W))
    for i in range(2, W):
        P = itertools.combinations(q_w, i)
        for p in P:
            q_w.append(p)
    q_w.append(W)

    q_h = list(range(H))
    for i in range(2, H):
        P = list(itertools.combinations(q_h, i))
        for p in P:
            q_h.append(p)
    q_h.append(H)
    q = list(itertools.product(q_h, q_w))

    while len(q) != 0:
        temp = copy.deepcopy(table)
        idxs_h, idxs_w = q.pop(0)
        if idxs_h != H:
            temp[idxs_h] = [0 for k in range(W)]
        if idxs_w != W:
            temp[:, idxs_w] = [0 for k in range(H)]

        if np.sum(temp) == K:
            # print(idxs_h, idxs_w)
            # print(temp)
            ans += 1

    print(ans)

resolve()

### FIXED CODE ###

def resolve():
    import numpy as np
    import itertools
    import copy

    H, W, K = map(int, input().split())
    table = []
    for _ in range(H):
        s = list(input())
        table.append(s)

    ans = 0
    for i in range(2**H):
        mask_h = format(i, '0{}b'.format(H))
        for j in range(2**W):
            mask_w = format(j, '0{}b'.format(W))
            black = 0
            for di in range(H):
                for dj in range(W):
                    if mask_h[di] == '0' and mask_w[dj] == '0' and table[di][dj] == "#":
                        black += 1
            if black == K:
                ans += 1
    print(ans)

resolve()
### BUGGY CODE ###

from itertools import combinations
import sys

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

min_diff = 10**9
max_diff = 1
min_sum = 2 * 10**9
max_sum = 2

for x,y in XY:
    min_diff = min(x-y, min_diff)
    max_diff = max(x-y, max_diff)
    min_sum = min(x+y, min_sum)
    max_sum = max(x+y, max_sum)

cand_set = set()
for x,y in XY:
    if x-y in (min_diff, max_diff) or x+y in (min_sum, max_sum):
        cand_set.add((x, y))

if len(cand_set) == N:
    print(max(max_sum-min_sum, max_diff - min_diff))
    sys.exit()

dist = 0
for p1, p2 in combinations(cand_set, 2):
    dist = max(dist, abs(p1[0]-p2[0]) + abs(p1[1]-p2[1]))
    
print(dist)

### FIXED CODE ###

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

min_diff = 10**9
max_diff = -10**9
min_sum = 2 * 10**9
max_sum = 2

for x,y in XY:
    min_diff = min(x-y, min_diff)
    max_diff = max(x-y, max_diff)
    min_sum = min(x+y, min_sum)
    max_sum = max(x+y, max_sum)

print(max(max_sum-min_sum, max_diff-min_diff))
### BUGGY CODE ###

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

ans = 0
while(len(b)>0):
    a1 = a.pop(0)
    b1 = b.pop(0)
    if a1 < b1:
        if a[0]+a1 <= b1:
            ans += a[0]+a1
            a[0] = 0
        else:
            ans += b1
            a[0] -= b1-a1
    else:
        ans += b1
    # print(a,b,ans)

print(ans)


### FIXED CODE ###

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

ans = 0
f1 = min(a[0], b[0])
f = [[f1, min(a[1], b[0]-f1)]]
for i in range(1,n):
    f_tmp = min(a[i]-f[i-1][1], b[i])
    f.append([f_tmp, min(a[i+1], b[i]-f_tmp)])
for f_i in f:
    ans += f_i[0]+f_i[1]
print(ans)
### BUGGY CODE ###

# dp[w] i番目までの品物で、重さがw以下になるよう選んだときの価値の最大値。
# 品物を増やすごとに、配列を更新して使いまわす。
# 重さは1~W 添え字は0<=w<=W<W+1 dpリストの長さはW+1
# ループは1~N回回す　添え字は0<=i<=N-1<N
# 添え字i, i+1回目のループでのdp[j]の求め方 i+1番目の品物を選ぶかどうか？
# j-w(i)<0のとき、重量オーバーで選べない。dp[j]は変わらない
# j-w(i)>=0のとき、dp[j]=max(dp[j], dp[j-w(i)]+v(i))
# 配列は逆側から更新していく
# 解答はN回ループした後のdp[W+1]=dp[-1] 最後の値

# 入力
# 重さと価値はループのなかで都度取得する
N, W = map(int, input().strip().split())

# 初期化
dp = [0] * (W + 1)

# dpテーブル
for i in range(N):
    w, c = map(int, input().strip().split())
    for j in range(W, -1, -1):
        if j - w >= 0:
            dp[j] = max(dp[j], dp[j - w] + c)

print(dp[-1])

### FIXED CODE ###

# dp[w] i番目までの品物で、重さがw以下になるよう選んだときの価値の最大値。
# 参考 https://qiita.com/drken/items/68b8503ad4ffb469624c

import numpy as np

# 入力
# 重さと価値はループのなかで都度取得する
N, W = map(int, input().strip().split())

# 初期化
dp = np.zeros(W + 1, dtype='int64')

# dpテーブル
for i in range(N):
    w, v = map(int, input().strip().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w] + v)

print(dp[-1])
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
ans = 0
for i in range(1,100000):
    cnt =0
    for x in a:
        if abs(i-x) <= 1:
            cnt += 1
    ans = max(ans,cnt)
print(ans)

### FIXED CODE ###

import collections
N = int(input())
a = list(map(int,input().split()))
dic = collections.Counter(a)
ans = 0
for i in range(min(a),max(a)+1):
    cnt = dic[i-1]+dic[i]+dic[i+1]
    ans = max(ans,cnt)
print(ans)
### BUGGY CODE ###

a,b,x = map(int, input().split())

# a,b,x = map(int, "0 5 1".split())
cnt=0
for num in range(a, b+1, 1):

    if num % x == 0:
        cnt+=1
print(cnt)

### FIXED CODE ###

a,b,x = map(int, input().split())

# a,b,x = map(int, "9 9 2".split())
cnt=0

alfa = b//x + 1
beta = (a-1)//x + 1

print(alfa - beta)
### BUGGY CODE ###

from collections import deque

s=deque(list( input() ))
t=deque([]) #

cnt=0
while s!=deque([]):
  x=s.popleft()
  if len(t)>=2 and x=="C":
    q=t.pop()
    p=t.pop()
    if p=="A" and q=="B":
      cnt += 1
      s.appendleft("A")
      s.appendleft("C")
      s.appendleft("B")
    else:
      t.append(p)
      t.append(q)
      t.append(x)
      
  else:
    t.append(x)
        
#print(t,s)
print(cnt)

### FIXED CODE ###

from collections import deque

s=input()
s=s.replace("BC","D")
N=len(s)

cnt=0
cntA=0
cntD=0

for i in range(N):
  if s[i]=="A":
    cntA += 1
  elif s[i]=="D":
    cnt += cntA
  else:
    cntA=0
    cntD=0
    
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
sys.setrecursionlimit(10**9)

def solve(x):
    def dp(x):
        if x == 0:
            return True
        elif x < 0:
            return False
        for i in range(100,106):
            if dp(x-i):
                return True
        return False

    return dp(x)



def main():
    X = int(input())
    print(int(solve(X)))
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def solve(x):
    if x >= 2000:
        return True
    memo = [True] + [False]*x

    def dp(k):
        if k == 0:
            return True
        for i in range(100,106):
            if k-i >= 0 and memo[k-i]:
                return True
        
        return False
    
    for i in range(x):
        memo[i+1] = dp(i+1)
    return memo[x]



def main():
    X = int(input())
    print(int(solve(X)))
    return

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

import bisect
import math
N = int(input())
A = list(map(int, input().split()))
T = [2 ** i for i in range(int(math.log2(max(A))) + 1, -1, -1)]

A.sort()

def is_in(t):
    i = bisect.bisect_left(A, t)
    if i < len(A) and t == A[i]:
        return i
    return -1

res = 0
while A:
    a = A.pop()
    T2 = [t - a for t in T if a < t <= 2 * a]
    for t in T2:
        i = is_in(t)
        if i != -1:
            res += 1
            del A[i]
            break

print(res)



### FIXED CODE ###

import bisect
import math
N = int(input())
A = list(map(int, input().split()))
T = [2 ** i for i in range(31)]
A.sort()
already = set()


def to_dic(A):
    d = {}
    for a in A:
        d[a] = d.setdefault(a, 0) + 1

    return d

def is_in(t, num):
    i = D.setdefault(t, 0)
    if i == 0:
        return 0
    s = min(i, num)
    D[t] -= s
    return s


res = 0
D = to_dic(A)
A2 = list(D.keys())
A2.sort()

for n in range(len(A2) - 1, -1, -1):
    a = A2[n]

    if a in T:
        res += D[a] // 2
        D[a] = 0

        if D[a] % 2 == 0:
            continue

    num = D[a]
    t = 1 << (int(math.log2(a)) + 1)

    while t > a:
        s = is_in(t - a, num)
        res += s
        num -= s
        if num == 0:
            break

        t >>= 1

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

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

# input
N = int(input())
X = list(map(int, input().split()))

# solve
for i in range(len(X)):
    X_ = list(X)
    X_.pop(i)
    X_ = sorted(X_)
    print(X_[int((len(X_)+1)/2-1)])


### FIXED CODE ###

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

# input
N = int(input())
X = list(map(int, input().split()))

# solve
X_sorted = sorted(X)
n0 = X_sorted[int(len(X_sorted)/2-1)]
n1 = X_sorted[int(len(X_sorted)/2)]
for i in range(len(X)):
    if (n1 > X[i]):
        print(n1)
    elif (n0 <= X[i]):
        print(n0)
### BUGGY CODE ###

a,b,c,k = map(int,input().split(" "))
for i in range(k):
	newa = b+c
	newb = a+c
	newc = a+b
	a = newa
	b = newb
	c = newc
if abs(a)>(10**18):
	print("Unfair")
else:
	print(a-b)

### FIXED CODE ###

a,b,c,k = map(int, input().split(" "))
if abs(a-b)>10**18:
    print("Unfair")
if k%2==0:
    print(a-b)
else:
    print(b-a)
### BUGGY CODE ###

N = int(input())

def prime_factorize(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

l = prime_factorize(N)
ans = 10 ** 12
for i in range(2**len(l)):
    a = 1
    b = 1
    for j in range(len(l)):
        if (i>>j & 1):
            a *= l[j]
        else:
            b *= l[j]
    if ans > a - 1 + b - 1:
        ans = a - 1 + b - 1
    
print(ans)

### FIXED CODE ###

N = int(input())

ans = 10**12 * 2
for i in range(1, int(N**0.5) + 1):
    if N % i == 0:
        distance = i + N//i - 2
        if ans > distance:
            ans = distance

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

def m():
    n, m = map(int, input().split())
    bridge = [1 for _ in range(n)]
    g = []
    for _ in range(m):
        a, b = map(int, input().split())
        g.append((a, b))
    g.sort(key=lambda x: x[1])
    cnt = 0
    for e in g:
        f = 0
        for j in range(e[0], e[1]):
            if bridge[j] == 0:
                f = 1
                break
        if f:
            continue
        # if bridge[e[0]:e[1]].count(0):
        #     continue
        bridge[e[1]-1] = 0
        cnt += 1
    return cnt

print(m())

### FIXED CODE ###

def m():
    n, m = map(int, input().split())
    bridge = [1 for _ in range(n)]
    g = []
    for _ in range(m):
        a, b = map(int, input().split())
        g.append((a, b))
    g.sort(key=lambda x: x[1])
    cnt = 0
    for e in g:
        f = 0
        for j in range(e[1]-1, e[0]-1, -1):
            if bridge[j] == 0:
                f = 1
                break
        if f:
            continue
        # if bridge[e[0]:e[1]].count(0):
        #     continue
        bridge[e[1]-1] = 0
        cnt += 1
    return cnt

print(m())
### BUGGY CODE ###

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

dp = [10**18] * (H + 1)
dp[0] = 0
for a, b in AB:
    for h in range(H + 1):
        r = min(H, h + a)
        if dp[r] > dp[h] + b:
            dp[r] = dp[h] + b
print(dp[H])


### FIXED CODE ###

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

dp = [10**10] * (H + 1)
dp[H] = 0

for a, b in AB:
    for h in range(H + 1)[:: -1]:
        dp[h] = min(dp[h], dp[min(H, h + a)] + b)

print(dp[0])
### BUGGY CODE ###

S=(input())
Q=int(input())
cnt_re=0
for i in range(Q):
    q=input().split()
    if q[0]=='1':
        cnt_re+=1
    else:
        tmp=cnt_re%2
        if ((q[1]=='1')&(tmp==0)) | ((q[1]=='2')&(tmp==1)):
            S=q[2]+S
        elif ((q[1]=='1')&(tmp==1)) | ((q[1]=='2')&(tmp==0)):
            S=S+q[2]
S=list(S)
if cnt_re%2==1:
    S.reverse()
print(''.join(S))

### FIXED CODE ###

S=(input())
Q=int(input())
cnt_re=0
s=''
for i in range(Q):
    q=list(input().split())
    if q[0]=='1':
        cnt_re+=1
    else:
        if (int(q[1])+cnt_re)%2==1:
            s=s+q[2]
        else:
            S=S+q[2]
if cnt_re%2==1:
    print(S[::-1]+s)
else:
    print(s[::-1]+S)
### BUGGY CODE ###

N, M = [int(n) for n in input().split()]

check_list = [0] * N

for i in range(M):
    l, r = [int(n) for n in input().split()]
    for j in range(l-1, r):
        check_list[j] += 1

print(check_list.count(M))

### FIXED CODE ###

N, M = [int(n) for n in input().split()]

l, r = 1, 10**5
for i in range(M):
    l_, r_ = [int(n) for n in input().split()]
    l = max(l, l_)
    r = min(r, r_)

if l > r:
    print(0)
else:
    print(r-l+1)
### BUGGY CODE ###


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

ld={}
for i in range(n):
    ld.setdefault(i,l[i])

ans=0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if ld[i]+ld[j]>ld[k] and ld[j]+ld[k]>ld[i] and ld[k]+ld[i]>ld[j]:
                ans+=1
            #print(l[i],l[j],l[k])

print(ans)


### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
ls = sorted(l)

ld={}
for i in range(n):
    ld.setdefault(i,ls[i])
#print(ld)

ans=0
for i in range(n-2):
    for j in range(i+1, n-1):
        k = bisect.bisect_left(ls, ld[i]+ld[j])
        #print(k)
        ans += k-j-1

print(ans)