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

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
from decimal import *
import heapq
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

k = INT()
num = 0
for i in range(1, 10 ** 6 + 100):
    num *= 10
    num += 7
    if num % k == 0:
        print(i)
        exit()
print(-1)


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
from decimal import *
import heapq
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

k = INT()
l = len(str(k))
if k % 2 == 0:
    print(-1)
    exit()
dp = [-1 for _ in range(10 ** 6 + 100)]
for i in range(10 ** 6 + 100):
    if l > i + 1:
        continue
    elif l == i + 1:
        num = 0
        for _ in range(i):
            num *= 10
            num += 7
        if k > num:
            continue
    if dp[i - 1] == -1:
        num = 0
        for _ in range(i):
            num *= 10
            num += 7
        dp[i] = num % k
    else:
        dp[i] = (dp[i - 1] * 10 + 7) % k
    if dp[i] == 0:
        print(i)
        exit()
print(-1)
### BUGGY CODE ###


n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]
enuq = list(enumerate(qs))
 
enuq.sort(key = lambda x:x[1][0])
ansli = [0 for i in range(q)]


for (i,(p,q)) in enuq:
    removelist=[]
    for (j,(l,r)) in enumerate(rails):
        if p<=l and r<=q:
            ansli[i]=ansli[i]+1
        elif l<p:
            removelist.append(j)
    for jj in sorted(removelist,reverse=True):
        rails.pop(jj)



for a in ansli:
    print(a)


### FIXED CODE ###

from collections import Counter
from itertools import product

n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]

xlist = [[0 for j in range(n)] for i in range(n)]
sumlist = [[0 for j in range(n+1)] for i in range(n)]
for (l,r),i in Counter(rails).items():
    xlist[l-1][r-1]=i


for (i,j) in product(range(n),range(n)):
    sumlist[i][j+1]=sum(xlist[i][0:j+1])


for (p,q) in qs:
    ans = 0
    for i in range(p-1,q):
        ans = ans+sumlist[i][q]-sumlist[i][p-1]
    print(ans)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
        
N,Q = (int(i) for i in input().split())
A = [() for i in range(N)]

for _ in range(N-1):
    a,b = (int(i) for i in input().split())
    A[a-1] += (b-1,)
    A[b-1] += (a-1,)

cnt = [0]*N   
for q in range(Q):
   p,x = (int(i) for i in input().split())
   cnt[p-1] += x

st = deque([(0,-1)])
while st:
    n,par = st.popleft()
    val = cnt[n]   
    for node in A[n]:
        if node == par:
            continue
        else:
            cnt[node] += val
            st.append([node,n])

print(*cnt)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
        
N,Q = (int(i) for i in input().split())
A = [[] for _ in range(N)]

for _ in range(N-1):
    a,b = (int(i) for i in input().split())
    A[a-1].append(b-1)
    A[b-1].append(a-1)

cnt = [0]*N   
for q in range(Q):
   p,x = (int(i) for i in input().split())
   cnt[p-1] += x

st = deque([(0,-1)])
while st:
    n,par = st.popleft()
    val = cnt[n]   
    for node in A[n]:
        if node == par:
            continue
        else:
            cnt[node] += val
            st.append([node,n])

print(*cnt)
### BUGGY CODE ###

N,M = map(int,input().split())
dic = {}
for _ in range(N):
    a,b = map(int,input().split())
    if a > M:
        pass
    else:
        if a in dic.keys():
            dic[a].append(b)
        else:
            dic[a] = [b]
lis = [[]] * M
for p in dic.keys():
    lis[M-p] = dic[p]
g = 0
for j in range(M):
    id = 0
    m =  0
    for w,k in enumerate(lis[j:]):
        if k != []:
            if m < max(k):
                m = max(k)
                id = w
    if m != 0:
        g += m
        lis[id+j].remove(m)
print(g)

### FIXED CODE ###

import heapq
n,m= map(int,input().split())
feeindays = [[] for _ in range(m)]
for i in range(n):
    a,b= map(int,input().split())
    if a<=m:feeindays[a-1]+=[b]
q=[]
heapq.heapify(q)
pay=0
for l in feeindays:
    for c in l:heapq.heappush(q,-c)
    if len(q)!=0:pay+=-1 * heapq.heappop(q)
print(pay)
### BUGGY CODE ###

import heapq
def dijkstra(x,route):
    n=len(route)
    d=[10**10]*n
    d[x]=0
    Visited=[False]*n
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        Visited[u]=True
        for v,cost in route[u]:
            if (not Visited[v]) and d[v]>d[u]+cost:
                d[v]=d[u]+cost
                heapq.heappush(hq,(d[v],v))
    return d

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

import sys
input=sys.stdin.readline
sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Edges=[[] for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Edges[i].append((j,d))
        Edges[j].append((i,d))
print(dijkstra(0,Edges)[-1])

### FIXED CODE ###

import sys
input=sys.stdin.readline

def dijkstra(s,n,Cost):
    D=[float('inf')]*n
    Visited=[False]*n
    D[s]=0
    while True:
        v=-1
        for i in range(n):
            if (not Visited[i]) and v==-1:
                v=i
            elif (not Visited[i]) and D[i]<D[v]:
                v=i
        if v==-1:
            break
        Visited[v]=True
        for j in range(n):
            D[j]=min(D[j],D[v]+Cost[v][j])
    return D

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Cost=[[float('inf')]*(n+2)for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Cost[i][j]=d; Cost[j][i]=d
print(dijkstra(0,n+2,Cost)[-1])
### BUGGY CODE ###

def solve(a):
    a=sorted(a)
    ans=a[0]#暫定最小

    if len(set(a))!=1:
        for _ in range(a[0]):
            for i in range(n):
                amari=a[i]%ans
                
                if amari>0:
                    if amari<ans:
                        ans=amari
                    else:
                        exit()
            if ans==1:
                break
    print(ans)


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

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
import fractions as ft


ans=a[0]
for i in a:
    ans=ft.gcd(ans,i)
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = np.array([int(i) for i in input().split()])
    b = np.array([int(i) for i in input().split()])

    if a.sum() < b.sum():
        print(-1)
        exit()

    diff = a - b
    org_diff = np.array(diff)

    def move(num):
        max_i = np.argmax(diff)
        max_v = diff[max_i]
        if max_v > num:
            diff[max_i] -= num
        else:
            diff[max_i] = 0
            move(num - max_v)

    for i in range(n):
        if diff[i] >= 0:
            continue
        move(-diff[i])
        diff[i] = 0
    diff -= org_diff
    print(sum([1 for i in diff if i != 0]))
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def main():
    N = int(input())
    A = map(int, input().split())
    B = map(int, input().split())

    sum = 0
    ans = 0
    rest = []
    for a, b in zip(A, B):
        if b > a:
            sum += b - a
            ans += 1
        else:
            rest.append(a - b)
    rest.sort(reverse=True)

    if sum <= 0:
        print(0)
        exit()

    for r in rest:
        sum -= r
        ans += 1
        if sum <= 0:
            break
    if sum > 0:
        print(-1)
    else:
        print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

S = [0 for i in range(300000)]
S2 = []
A = [-1, 1]
for i in range(1, int(300000 / 7) + 1):
    d = 7 * i
    for a in A:
        da = d + a
        if da < 300000 and S[da] == 0:
            S2.append(str(da))
            for j in range(2, int(300000 / 2)):
                if da * j >= 300000:break
                S[da * j] = -1
while 1:
    n = int(input())
    if n == 1:break
    #res = [str(n) + ':']
    #res += [x for x in S2 if int(x) <= n and n % int(x) == 0]
    print(str(n) + ':',' '.join([x for x in S2 if int(x) <= n and n % int(x) == 0]))

### FIXED CODE ###

S = [0 for i in range(300000)]
S2 = []
A = [-1, 1]
for i in range(1, int(300000 / 7) + 1):
    d = 7 * i
    for a in A:
        da = d + a
        if da < 300000 and S[da] == 0:
            S2.append(da)
            for j in range(2, int(300000 / 2)):
                if da * j >= 300000:break
                S[da * j] = -1
while 1:
    n = int(input())
    if n == 1:break
    print(str(n) + ':',' '.join([str(x) for x in S2 if n % x == 0 and x <= n]))
### BUGGY CODE ###

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

bl = []

for i in range(n-1):
    bl.append(xl[i+1] - xl[i])

import math
a = math.factorial(n-1)
c = a
ans = 0

for i in range(n-1):
    ans += c * bl[i]
    ans %= 10**9 + 7
    c += a // (i+2)

print(ans)

### FIXED CODE ###

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

bl = []

for i in range(n-1):
    bl.append(xl[i+1] - xl[i])

import itertools
bl_ac = list(itertools.accumulate(bl))

MOD = 10**9 + 7
N = 10**5

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

ans = 0
p = 1
c = 1
for i in range(n-1):
    ans += bl[i] * perm(n-1, n-2-i) * c
    ans %= MOD
    c *= i + 2
    c += p
    c %= MOD
    p *= i + 2
    p %= MOD

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

while True:
    n = int(raw_input())
    if n == 0:
        break
    a = [0] * n
    for i in range(n):
        a[i] = int(raw_input())
    r = a[0]
    for i in range(n+1):
        for j in range(i+1, n+1):
            r = max(r, sum(a[i:j]))
    print r

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0:
        break
    a = [0] * n
    dp = [0] * n
    for i in range(n):
        a[i] = int(raw_input())
        if i == 0:
            dp[0] = a[0]
        else:
            dp[i] = max(dp[i-1]+a[i], a[i])
    print max(dp)
### BUGGY CODE ###

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

x=0
y=max(A)

def f(l):
  nums=0
  for a in A:
    t=1
    while a/t>l:
      t+=1
    nums+=t-1
  if nums>K:
    return False
  else:
    return True

while y-x>1:
  tmp=(x+y)//2
  if f(tmp)==True:
    y=tmp
  else:
    x=tmp
    
print(y)

### FIXED CODE ###

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

x=0
y=max(A)

def f(l):
  nums=0
  for a in A:
    if a%l==0:
      nums+=a//l-1
    else:
      nums+=a//l
  if nums>K:
    return False
  else:
    return True

while y-x>1:
  tmp=(x+y)//2
  if f(tmp)==True:
    y=tmp
  else:
    x=tmp
    
print(y)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline
N, W = map(int, input().split())
def knapsack():
  dp = np.zeros((N+1, W+1), dtype=int)
  c = np.arange(1, N+1)
  cc = np.arange(1, W+1)
  for i in c:
    w, v = map(int, input().split())
    for sum_w in cc:
      if sum_w - w >= 0:
        dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-w] + v)
      dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])
  return dp[-1][-1]
print(knapsack())

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline
N, W = map(int, input().split())
def knapsack():
  dp = np.zeros((N+1, W+1), dtype=int)
  c = np.arange(1, N+1)
  for i in c:
    w, v = map(int, input().split())
    dp[i][w:] = np.maximum(dp[i-1][w:], dp[i-1][:-w] + v)
    dp[i][:] = np.maximum(dp[i][:], dp[i-1][:])
  return dp[-1][-1]
print(knapsack())
### BUGGY CODE ###

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

mylist=[[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    l,r=map(int,input().split())
    mylist[l][r]+=1

for i in range(1,n+1):
    for j in range(1,n+1):
        mylist[i][j]+=mylist[i][j-1]

for i in range(q):
    P,Q=map(int,input().split())
    tmp=0
    for j in range(P,Q+1):
        tmp+=mylist[j][Q]
    print(tmp)

### FIXED CODE ###

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

mylist=[[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    l,r=map(int,input().split())
    mylist[l][r]+=1

for i in range(1,n+1):
    for j in range(1,n+1):
        mylist[i][j]+=mylist[i][j-1]

memo=[[-1]*(n+1) for _ in range(n+1)]

for i in range(q):
    P,Q=map(int,input().split())
    if(memo[P][Q]!=-1):
        print(memo[P][Q])
        continue
    tmp=0
    for j in range(Q,P-1,-1):
        tmp+=mylist[j][Q]
        memo[j][Q]=tmp
    print(tmp)
### BUGGY CODE ###

#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3

S = input()
size = len(S)
L = [0] * 2019

tmp = int(S[size-1])  # 最後の文字
L[0] = 1
L[tmp] += 1

for i in reversed(range(size - 1)):  # 最後の文字の一つ手前からループを回す
    d = size - i  # 今の桁数(10の何乗になるのか)
    n = int(S[i])  # 対象の文字
    r = (n * (10 ** (d - 1))) % 2019  # 2019で割った余り
    tmp = (tmp + r) % 2019
    # print(f"{i}桁目:{tmp}")
    L[tmp] += 1

ans = 0
for i in range(2019):
    tmp = L[i]
    if (tmp > 1):
        ans += tmp * (tmp - 1) // 2

print(ans)


### FIXED CODE ###

#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3

S = input()
size = len(S)
L = [0] * 2019

tmp = int(S[size - 1])  # 最後の文字
L[0] = 1
L[tmp] += 1
tmp_r = 1  # 10のn乗を2019で割った余り(n初期値: 1)

for i in reversed(range(size - 1)):  # 最後の文字の一つ手前からループを回す
    n = int(S[i])  # 対象の文字
    tmp_r = (tmp_r*10) % 2019
    r = (n * tmp_r) % 2019
    tmp = (tmp + r) % 2019
    # print(f"{i}桁目:{tmp}")
    L[tmp] += 1

ans = 0
for i in range(2019):
    tmp = L[i]
    if (tmp > 1):
        ans += tmp * (tmp - 1) // 2


def calc(i):
    if (i == 0):
        return


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

import collections

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

cnt = 0

while len(A) > K:
    min_k = min(A, key=A.get)
    cnt += A[min_k]
    A.pop(min_k)

print(cnt)

### FIXED CODE ###

import collections

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = dict(collections.Counter(A))
A = sorted(A.items(), key=lambda x: x[1], reverse=True)

cnt = 0

for i in range(N):
    if len(A) > K:
        cnt += A[-1][1]
        A.pop()
    else:
        break

print(cnt)
### BUGGY CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def cmb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p))%p

x, y = MAP()
a = 2*x - y
b = 2*y - x

if a >= 0 and b >= 0 and a % 3 == 0 and b % 3 == 0:
    a //= 3
    b //= 3
    ans = cmb(a+b, a, 10**9+7)
else:
    ans = 0

print(ans)

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

x, y = MAP()
a = 2*x - y
b = 2*y - x

if a >= 0 and b >= 0 and a % 3 == 0 and b % 3 == 0:
    a //= 3
    b //= 3
    ans = cmb(a+b, a, 10**9+7)
else:
    ans = 0

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

n, m = map(int, input().split())
l, r = map(int, input().split())
key = set([l + i for i in range(r - l + 1)])
for i in range(m - 1):
    l, r = map(int, input().split())
    key &= set([l + i for i in range(r - l + 1)])
print(len(key))

### FIXED CODE ###

n, m = map(int, input().split())
l0, r0 = map(int, input().split())
for i in range(m - 1):
    l, r = map(int, input().split())
    l0 = max(l0, l)
    r0 = min(r0, r)
print(max(0, r0 - l0 + 1))
### BUGGY CODE ###

a,b = map(int,input().split())
po = []
ne = []
ze = []
for i in range(a,b+1):
    if i < 0:
        ne.append(1)
    elif i > 0:
        po.append(1)
    else:
        ze.append(1)

if sum(ze) != 0:
    print("Zero")
elif sum(ne) % 2 == 0:
    print("Positive")
else:
    print("Negative")

### FIXED CODE ###

a,b = map(str,input().split())#整数を文字列として入力
S = a+b
P = S.count("-")
if P == 1:
  print("Zero")
elif P == 2:
  if (int(b) - int(a)) % 2 ==0:
    print("Negative")
  else:
    print("Positive")
else:
  print("Positive")
### BUGGY CODE ###

ab=[]

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

for i in range(m):
    ab.append(tuple(map(int,input().split())))

    ab.sort(key=lambda x:x[1])

res=0
toremove=set()
while(1):
    for j in range(len(ab)):
        if ab[0][1] > ab[j][0]:
            toremove.add(ab[j])
        #else:break
    if len(toremove)>0:
        for r in toremove:
            ab.remove(r)
        toremove=set()
        res+=1
    if len(ab) == 0:break

print(res)

### FIXED CODE ###

ab=[]

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

for i in range(m):
    ab.append(tuple(map(int,input().split())))

ab.sort(key=lambda x:x[1])

res=0
for z in range(len(ab)):
    x=ab[0][1]
    for j in range(len(ab)):
        if x > ab[0][0]:
            del ab[0]
        else:
            res+=1
            break
    if len(ab)==0:
        res+=1
        break
    
print(res)
### BUGGY CODE ###

N = int(input())
S = input()


R = []
B = []
G = []
p = 0
for i in S:
    if(i == "R"):
        R.append(p)
    elif(i == "B"):
        B.append(p)
    elif(i == "G"):
        G.append(p)
    p += 1
sum = len(R) * len(B) * len(G)
for r in R:
    for b in B:
        up = max(r, b)
        dw = min(r, b)
        d = up-dw
        if up + d in G:
            sum -= 1
        if dw - d in G:
            sum -= 1
        if (r+b)/2 in G:
            sum -= 1

print(sum)


            

### FIXED CODE ###

N = int(input())
S = input()


R = []
B = []
G = []
p = 0
for i in S:
    if(i == "R"):
        R.append(p)
    elif(i == "B"):
        B.append(p)
    elif(i == "G"):
        G.append(p)
    p += 1
R = set(R)
B = set(B)
G = set(G)
sum = len(R) * len(B) * len(G)
for r in R:
    for b in B:
        up = max(r, b)
        dw = min(r, b)
        d = up-dw
        if up + d in G:
            sum -= 1
        if dw - d in G:
            sum -= 1
        if (r+b)/2 in G:
            sum -= 1

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

n = int(input())
total = 0
for i in range(len(str(n))):
  total += int(str(n)[i])
if total % 9 == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n = input()
total = 0
for i in range(len(n)):
  total += int(n[i])
if total % 9 == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

inpl = lambda: list(map(int,input().split()))
N, M ,K = inpl()
MOD = 10**9+7
factor = 1
# MN-2 C K-2 = MN-2 C MN-K = MN-2 C L
L = min(K-2,M*N-K)
for i in range(M*N-L-1,M*N-1):
    factor *= i
for i in range(1,L+1):
    factor //= i
factor %= MOD
ans = ((M*(N-1)*(N+1) + N*(M-1)*(M+1))*M*N //6 * factor) % MOD
print(ans)

### FIXED CODE ###

inpl = lambda: list(map(int,input().split()))
N, M ,K = inpl()
MOD = 10**9+7

def mod_inv(a, m=MOD):
    def mod_inv_sub(a, m):
        if a == 1:
            return 1, 0
        else:
            d, r = m//a, m % a
            x, y = mod_inv_sub(r, a)
            return y - d*x, x

    x = mod_inv_sub(a,m)[0]
    if x < 0:
        x += (-x//m + 1) * m
    return x

factor = 1
# MN-2 C K-2 = MN-2 C MN-K = MN-2 C L
L = min(K-2,M*N-K)
for i in range(M*N-L-1,M*N-1):
    factor = factor * i % MOD
for i in range(1,L+1):
    factor = factor * mod_inv(i) % MOD
ans = ((M*(N-1)*(N+1) + N*(M-1)*(M+1))*M*N //6 * factor) % MOD
print(ans)
### BUGGY CODE ###

import time

time.sleep(3)
a, b = map(int, input().split())
print(max(a + b, a - b, a * b))

### FIXED CODE ###

a, b = map(int, input().split())
print(max([a + b, a - b, a * b]))
### BUGGY CODE ###

#171D
#Replacing
#自分の解き方

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
L=len(A)
S=sum(A)

for i in range(Q):
    ans=0
    B,C=map(int,input().split())
    for j in range(L):
        if A[j]==B:
            A[j]=C
            S+=(C-B)
    ans=S
    print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))
C = Counter(A)
ans = sum(A)
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    if c not in C.keys():
        C[c] = 0
    if b in C.keys():
        ans += (c-b)*C[b]
        C[c] += C[b]
        C[b] = 0
    print(ans)