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

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(N - 1 + M)]

from collections import defaultdict
from copy import deepcopy

vs = defaultdict(set)
ws = defaultdict(set)

for a, b in AB:
    vs[a].add(b)
    ws[b].add(a)

rws = deepcopy(ws)

#print(vs)
#print(ws)

# topological sort

L = []
S = [i for i in range(1, N + 1) if not ws[i]]

while S:
    n = S.pop()
    L.append(n)
    for m in vs[n]:
        rws[m].remove(n)
        if not rws[m]:
            S.append(m)

#print(S)
#print(L)

nrank = {}

for r, n in enumerate(L):
    nrank[n] = r

#print(nrank)

for n in range(1, N + 1):
    r = 0
    if ws[n]:
        r = sorted(ws[n], key=lambda x:-nrank[x])[0]
    print(r)


### FIXED CODE ###

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(N - 1 + M)]

import sys
sys.setrecursionlimit(200000)

from collections import defaultdict

vs = defaultdict(set)
ws = defaultdict(set)

for a, b in AB:
    vs[a].add(b)
    ws[b].add(a)

#print(vs)
#print(ws)

L = []

cs = [0] * (1 + N)

def visit(n):
    if cs[n] == 1:
        return
    elif cs[n] == 0:
        cs[n] = 1
        for m in vs[n]:
            visit(m)
        cs[n] = 2
        L.append(n)

for n in range(1, N + 1):
    if cs[n] == 0:
        visit(n)

#print(L)

nrank = {}

for r, n in enumerate(L):
    nrank[n] = r

#print(nrank)

for n in range(1, N + 1):
    r = 0
    if ws[n]:
        r = sorted(ws[n], key=lambda x:nrank[x])[0]
    print(r)
### BUGGY CODE ###

# 文字数を入力
length = int(input())
# テキストを1文字ずつのリストで入力
text = list(input())
# 組み合わせの数のカウント変数
count = 0
# 総当たりで組み合わせを調べる
for i, c1 in zip(range(1, length+1), text[0:]):
    for j, c2 in zip(range(i+1, length+1), text[i:]):
        for k, c3 in zip(range(j+1, length+1), text[j:]):
            if (j - i != k - j) and (c1 != c2 and c1 != c3 and c2 != c3):
                count += 1
print(count)

### FIXED CODE ###

length = int(input())
text = input()

r_count = text.count("R")
g_count = text.count("G")
b_count = text.count("B")

answer = r_count * g_count * b_count

for i in range(length-2):
    for j in range(i+1, length-1):
        k = i + (j-i)*2
        if k < length and text[i]!=text[j] and text[i]!=text[k] and text[j]!=text[k]:
            answer -= 1
        
print(answer)
### BUGGY CODE ###

import sys
if sys.version_info.minor < 5:
    from fractions import gcd
else:
    from math import gcd
import math

A, B = map(int, input().split())
g = gcd(A, B)

ans = [1]
for i in range(2, g+1):
    # print("i: {}".format(i))

    if g % i == 0:
        # print("This is a cd of A and B.")
        ans.append(i)

    while g % i == 0:
        g /= i

# print(set(ans))

print(len(set(ans)))


### FIXED CODE ###

import sys
if sys.version_info.minor < 5:
    from fractions import gcd
else:
    from math import gcd
import math

DEBUG = False

A, B = map(int, input().split())
g = gcd(A, B)
if DEBUG:
    print("gcd(A, B): {}".format(g))

ans = [1]
i= 2
temp = g
while i <= int(-(-g**0.5//1))+1:
    if DEBUG:
        print("i: {}, g: {}".format(i, g))

    if temp % i == 0:
        if DEBUG:
            print("This is a cd of A and B.")
        ans.append(i)

    while temp % i == 0:
        temp //= i

    i += 1

if temp != 1:
    ans.append(temp)

if DEBUG:
    print(ans)

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

n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
    return gcd(b,a%b) if b else a
def lcm(a,b):
    return a*b//gcd(a,b)
k=1
for i in range(n):
    k = lcm(k,a[i])
ans=0
for i in range(n):
    ans += k//a[i]
    ans %= 1000000007
print(ans)


### FIXED CODE ###

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

def gcd(a,b):
    return gcd(b,a%b) if b != 0 else a
mod = 10**9+7

def lcm(a,b):
    return a*b%mod * pow(gcd(a,b),mod-2,mod) % mod

num = {}

for i in range(n):
    nown=a[i]
    tmp = {}
    for i in range(2,int(nown**0.5) + 5):
        while nown % i ==0:
            nown//=i
            if(i in tmp):
                tmp[i]+=1
            else:
                tmp[i] = 1
    if nown != 1:
        tmp[nown] = 1    
    for key in tmp:
        if (key in num):
            num[key] = max(num[key],tmp[key])
        else:
            num[key] = tmp[key]

kobai = 1
for key in num:
    kobai *= pow(key, num[key],mod)
    kobai %= mod
    
ans = 0

for i in range(n):
    ans += kobai * pow(a[i],mod-2,mod) %mod
    ans %= mod

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

a, b, n = map(int, input().split())
ans = 0
for i in range(n+1):
  ans = max(ans, int(a*i/b)-a*int(i/b))
print(ans)

### FIXED CODE ###

a, b, n = map(int, input().split())
ans = 0
e = min(n+1,b)
s = max(int(b/a),e-1000)
for i in range(s, e):
  x = (int(a*i/b)-a*int(i/b))
  if ans < x:
    ans = x
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
t = []

def F(f,fr,ba,c):
  if f == '1':
     return c + fr, ba
  if f == '2':
    return fr, ba + c

def R(r):
  if r == '1':return '2'
  if r == '2':return '1'

fr = ''
ba = ''
r = '1'
for n in range(q):
  t = input().split()
  if t[0] == '1':
    r = R(r)
  else:
    if r =='2':
      t[1] = R(t[1])
    fr,ba = F(t[1],fr,ba,t[2])


    
if r == '1': 
   print(fr + s + ba)
else:
  a = ''
  ans = fr + s + ba
  for n in ans:
    a = n + a
  print(a)



### FIXED CODE ###


s = input()
q = int(input())
t = []
 
def F(f,fr,ba,c):
  if f == '1':
     return c + fr, ba
  if f == '2':
    return fr,ba + c

def R(r):
  if r == '1':return '2'
  if r == '2':return '1'

ans = s
fr = ''
ba = ''
r = '1'
for n in range(q):
  t = input().split()
  if t[0] == '1':
    r = R(r)
  else:
    if r =='2':
      t[1] = R(t[1])
    fr, ba = F(t[1],fr,ba,t[2])
 
    
if r == '1': 
   print(fr + ans + ba)
else:
  print(ba[::-1] + ans[::-1]+ fr[::-1])
### BUGGY CODE ###

A, B, K = map(int, input().split())
while (K > 0):
  if A > 0:
    A -= 1
  elif B > 0:
    B -= 1
  K -= 1
print(str(A) + " " + str(B))

### FIXED CODE ###

A, B, K = map(int, input().split())
if A >= K:
  print(A - K, B)
elif B >= (K - A):
  print(0, B - (K - A))
else:
  print(0, 0)
### BUGGY CODE ###

n,k=map(int,input().split())
P=list(map(int,input().split()))
for i in range(n):
    P[i]=sum(range(P[i]+1))/P[i]

s=[]
for i in range(n-k+1):
    s.append(sum(P[i:i+k]))

print(max(s))

### FIXED CODE ###

n,k=map(int,input().split())
P=list(map(int,input().split()))
for i in range(n):
    P[i]=0.5*(P[i]+1)
x=sum(P[:k])
s=[x]

for i in range(1,n-k+1):
    x=x-P[i-1]+P[i+k-1]
    s.append(x)

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

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

A.sort()
if N % 2 == 1:
    if A.count(0) != 1:
        print(0)
        quit()
    s = 2
else:
    s = 1

for i in range(s, N, 2):
    if A.count(i) != 2:
        print(0)
        quit()
print(2**(N//2))


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))

if N % 2 == 1:
    if A.count(0) != 1:
        print(0)
        quit()

c = {}
for e in A:
    if e == 0:
        continue
    if e in c.keys():
        c[e] += 1
    else:
        c[e] = 1
if all([x == 2 for x in c.values()]):
    print(2**(N//2)%(10**9+7))
else:
    print(0)
### BUGGY CODE ###

N,x=map(int,input().split())
A=[int(x) for x in input().split()]
dp=[[int(x) for x in A] for i in range(2)]

#dp[i]:k回魔法を唱えた時にA[i]を手に入れる最小の時間。
#dp=Aで初期化。その後、１〜Nまでのdp[i]はmin(dp[i-1],A[i])で順に更新されていく。
#更新前後のdpを保持するため蟻本P60に記載のある「配列の再利用」を行う。
#各回におけるsum(dp)+k*xを算出して最小値が答え。

#ans初期値は魔法を唱えず、全てを入手した数字（sum(A))
ans=sum(A)
for k in range(1,N):
  cnt=0
  for i in range(N):
    dp[(k+1)&1][i]=min(dp[k&1][i-1],A[i])
    cnt+=dp[(k+1)&1][i]
  ans=min(ans,cnt+k*x)
  
print(ans)


### FIXED CODE ###

N,x=map(int,input().split())
A=[int(x) for x in input().split()]
dp=A[:]

#dp[i]:k回魔法を唱えた時にA[i]を手に入れる最小の時間。
#dp=Aで初期化。その後、１〜Nまでの各ステップでdp[i]はmin(dp[i],A[i-k])で順に更新されていく。
#各回におけるsum(dp)+k*xを算出して最小値が答え。

#ans初期値は魔法を唱えず、全てを入手した数字（sum(A))
ans=sum(A)
for k in range(1,N):
  for i in range(N):
    if dp[i]>A[i-k]:
      dp[i]=A[i-k]
  ans=min(ans,sum(dp)+x*k)

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

t = raw_input()
W, H = map(int, t.split(' '))
p, q = [], []
for i in xrange(W):
    p.append(int(raw_input()))
for j in xrange(H):
    q.append(int(raw_input()))

cost = 0
for i in xrange(W+1):
    for j in xrange(H+1):
        if i == 0 and j == 0: continue
        cost += min(p[i-1] if i > 0 else 100000005, q[j-1] if j > 0 else 100000005)
print cost

### FIXED CODE ###


import bisect
cost = 0
t = raw_input()
W, H = map(int, t.split(' '))
p, q = [], []
sum_p = []
for i in xrange(W):
    tmp = int(raw_input())
    p.append((i, tmp))
p.sort(key=lambda a: a[1])
pp = [each[1] for each in p]
for i in xrange(W):
    if not sum_p:
        sum_p.append(pp[i])
    else:
        sum_p.append(sum_p[-1]+pp[i])
cost += sum(pp)
for j in xrange(H):
    new = int(raw_input())
    cost += new
    minus = bisect.bisect_right(pp, new)
    cost += (W-minus) * new
    cost += sum_p[minus-1] if minus > 0 else 0

print cost
### BUGGY CODE ###

#16D8101012J 伊藤惇 dj Python3
import sys

def Maximum_Profit(n,A):
    Max=-sys.maxsize
    for i in range(n-1):
        tmp=(max(A[i+1:])-A[i])
        if Max<tmp:
            Max=tmp
    return Max

if __name__ == "__main__":
    n=int(input())
    A=[]
    for i in range(n):
        A.append(int(input()))
    Max=Maximum_Profit(n,A)
    print(Max)



### FIXED CODE ###

#16D8101012J 伊藤惇 dj Python3

def Maximum_Profit(n,A):
    Max=A[1]-A[0]
    Min=A[0]
    for j in range(1,n):
        Max=max(Max,A[j]-Min)
        Min=min(Min,A[j])
    return Max

if __name__ == "__main__":
    n=int(input())
    A=[]
    for i in range(n):
        A.append(int(input()))
    Max=Maximum_Profit(n,A)
    print(Max)
### BUGGY CODE ###

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

memo = {}
cnt_max = {}
for i in range(n):
    cnt_max[i] = 0
for i in range(n):
    memo[i] = 0

cnt = 0
while True:
    flag = False
    for i in range(n):
        if memo[i] == len(a[0]):
            continue
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            flag = True
            tmp = memo[i]
            max_1 = max(cnt_max[i], cnt_max[a[i][tmp] - 1])
            cnt_max[i] = max_1 + 1
            cnt_max[a[i][tmp] - 1] = max_1 + 1
            memo[i] += 1
            memo[a[i][tmp] - 1] += 1
    if flag:
        cnt += 1
    else:
        for i in memo:
            if memo[i] != len(a[0]):
                print(-1)
                exit()
        break
ans = 0
for i in cnt_max:
    ans = max(cnt_max[i] , ans)
print(ans)

### FIXED CODE ###

import time
s_time = time.time()


n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

memo = {}
for i in range(n):
    memo[i] = 0

cnt = 0
while True:
    visited = [False] * n
    flag = False
    for i in range(n):
        if memo[i] == len(a[0]):
            continue
        if visited[i] or visited[a[i][memo[i]] - 1]:
            continue
        visited[i] = True
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            visited[a[i][memo[i]] - 1] = True
            flag = True
            tmp = memo[i]
            memo[i] += 1
            memo[a[i][tmp] - 1] += 1
    if flag:
        cnt += 1
    else:
        for i in memo:
            if memo[i] != len(a[0]):
                print(-1)
                exit()
        break
    if abs(s_time - time.time()) > 1.7:
        print(n*(n-1) //2)
        exit()
print(cnt)
### BUGGY CODE ###

mod=10**9+7
s=input()
s=s[::-1]
dp=[[0]*13 for _ in range(len(s)+1)]
dp[0][0]=1
for i in range(len(s)):
	p=pow(10,i,13)
	if s[i]=="?":	
		for k in range(13):
			for j in range(10):
				dp[i+1][(k+p*j)%13]+=dp[i][k]
				dp[i+1][(k+p*j)%13]%=mod
	else:
		for k in range(13):
			dp[i+1][(k+p*int(s[i]))%13]+=dp[i][k]
			dp[i+1][(k+p*int(s[i]))%13]%=mod
print(dp[-1][5])


### FIXED CODE ###

mod=10**9+7
s=input()
s=s[::-1]
dp=[[0]*13 for _ in range(len(s)+1)]
dp[0][0]=1
for i in range(len(s)):
	p=pow(10,i,13)
	if s[i]=="?":	
		for k in range(13):
			for j in range(10):
				dp[i+1][(k+p*j)%13]+=dp[i][k]
				dp[i+1][(k+p*j)%13]%=mod
	else:
		for k in range(13):
			dp[i+1][(k+p*int(s[i]))%13]+=dp[i][k]
			dp[i+1][(k+p*int(s[i]))%13]%=mod
print(dp[-1][5])
### BUGGY CODE ###

T = list(input())
ans = ''
for i in range(-1,-len(T)-1,-1):
    if T[i] == '?' and i == -1:
        T[i] = 'D'
    elif T[i] == '?':
        if T[i+1] == 'D':
            T[i] = 'P'
        else:
            T[i] = 'D'
for i in range(len(T)):
    ans += T[i]
print(ans)

### FIXED CODE ###

T = list(input())
for i in range(len(T)):
    if T[i] == '?':
        T[i] = 'D'
print(''.join(T))
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque

h, w = list(map(int, input().split()))
s = [list(str(input())) for i in range(h)]

map_ = [[10**9]*w for i in range(h)]
# map_[0][0] = 10*

num_black = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            num_black += 1


dq = deque([[0, 0, 1]])


ans = 0
while(len(dq) > 0):
    y, x, dis = dq.popleft()

    if map_[y][x] > dis:
        map_[y][x] = dis
    else:
        continue

    for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if y+i < 0 or y+i >= h:
            continue
        if x+j < 0 or x+j >= w:
            continue
        if map_[y+i][x+j] <= dis:
            continue
        if s[y+i][x+j] == "#":
            continue
        else:
            dq.appendleft([y+i, x+j, dis+1])

ans = map_[-1][-1]
# print(map_)

if ans == 10**9:
    print(-1)
else:
    print(w*h-ans-num_black)


### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque

h, w = list(map(int, input().split()))
s = [list(str(input())) for i in range(h)]

map_ = [[10**9]*w for i in range(h)]
# map_[0][0] = 10*

num_black = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            num_black += 1


dq = deque([[0, 0, 1]])


ans = 0
while(len(dq) > 0):
    y, x, dis = dq.popleft()

    if map_[y][x] > dis:
        map_[y][x] = dis
    else:
        continue

    for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if y+i < 0 or y+i >= h:
            continue
        if x+j < 0 or x+j >= w:
            continue
        if map_[y+i][x+j] <= dis:
            continue
        if s[y+i][x+j] == "#":
            continue
        else:
            dq.appendleft([y+i, x+j, dis+1])

ans = map_[-1][-1]
# print(map_)

if ans == 10**9:
    print(-1)
else:
    print(w*h-ans-num_black)
### BUGGY CODE ###

class fenwick_tree:
    def __init__(self, n):
        self.data = [0 for _ in range(n+1)]
        self.n = n

    def add(self, p, x):
        p += 1
        while p <= self.n:
            self.data[p-1] += x
            p += p & -p
    
    def sum(self, l, r):
        return self._sum(r) - self._sum(l)

    def _sum(self, r):
        s = 0
        while r > 0:
            s += self.data[r-1]
            r -= r & -r
        return s
    
N, Q = [int(_) for _ in input().split()]

fw = fenwick_tree(N)
A = [int(_) for _ in input().split()]
for i, a in enumerate(A):
    fw.add(i, a)

for i in range(Q):
    t, *q = [int(_) for _ in input().split()]
    if t == 0:
        p, x = q
        fw.add(p, x)
    else:
        l, r = q
        print(fw.sum(l, r))


### FIXED CODE ###

class fenwick_tree:
    def __init__(self, n):
        self.data = [0 for _ in range(n+1)]
        self.n = n

    def add(self, p, x):
        p += 1
        while p <= self.n:
            self.data[p-1] += x
            p += p & -p
    
    def sum(self, l, r):
        return self._sum(r) - self._sum(l)

    def _sum(self, r):
        s = 0
        while r > 0:
            s += self.data[r-1]
            r -= r & -r
        return s
    
N, Q = [int(_) for _ in input().split()]

fw = fenwick_tree(N)
A = [int(_) for _ in input().split()]
for i, a in enumerate(A):
    fw.add(i, a)

for i in range(Q):
    t, *q = [int(_) for _ in input().split()]
    if t == 0:
        p, x = q
        fw.add(p, x)
    else:
        l, r = q
        print(fw.sum(l, r))
### BUGGY CODE ###

import sys
n,k = [int(_) for _ in input().split()]
base = n

if k == 1:
  print("0")
  sys.exit()

while base > abs(base - k):
  base = abs(base - k)

print(base)

### FIXED CODE ###

import sys
n,k = [int(_) for _ in input().split()]

amari = n % k
if amari == 0 :
  print("0")
  sys.exit()

base = amari
while base > abs(base - k):
  base = abs(base - k)

print(base)
### BUGGY CODE ###

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

dp = [1000000000] * N
dp[0] = 0

for i in range(N - 1):
    for j in range(1,K+1):
        if i+j < N:
            if dp[i + j] > abs(h[i + j] - h[i]) + dp[i]:
                dp[i + j] = abs(h[i + j] - h[i]) + dp[i]

print(dp[N - 1])

### FIXED CODE ###

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

dp = [1000000000] * N
dp[0] = 0

for i in range(N - 1):
    for j in range(1, K + 1):
        if i + j < N:
            if dp[i + j] > abs(h[i + j] - h[i]) + dp[i]:
                dp[i + j] = abs(h[i + j] - h[i]) + dp[i]
        else:
            break

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

n = int(input())
attends = [int(each) for each in input().split(' ')]
ordered = attends.copy()
ordered.sort()
for each in ordered:
    print(attends.index(each) + 1, end=' ')


### FIXED CODE ###

from operator import itemgetter
n = int(input())
ordered_info = [ [i, int(num)] for i, num in zip(range(n), input().split(' '))]
ordered_info.sort(key = itemgetter(1))
ans = ''
for i, _ in ordered_info:
    print(i+1, end=' ')
### BUGGY CODE ###

import numpy as np

#input = raw_input
N, M = map(int, input().split(" "))
prices = list(map(int, input().split(" ")))

prices = np.asarray(prices)

for i in range(M):
    #max_p = max(prices) 
    max_i = prices.argmax() 
    #max_i = prices.index(max_p)
    prices[max_i] //=  2 

#out = sum(prices)
out = prices.sum()
print(out)

### FIXED CODE ###

from heapq import heappush, heappop

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

prices = []
for price in map(int, input().split(" ")):
    heappush(prices, -price)


for i in range(M):
    max_p = - (heappop(prices))
    half_p = max_p // 2
    heappush(prices, - half_p)

out = - sum(prices)
print(out)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    S = list(input().rstrip())

    dec_a = [0] * (N)
    for x in range(1, N):
        if S[x] == 'C' and S[x-1] == 'A':
            S[x-1] = 'a'
        dec_a[x] = S[:x+1].count('a')


    L = [0] * Q
    R = [0] * Q
    for i in range(Q):
        L[i], R[i] = map(int, input().split())

    for j in range(Q):
        print(dec_a[R[j]-1] - dec_a[L[j]-1])

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    S = input().rstrip()

    cnt_ac = 0
    arr_ac = [0] * (N)
    for x in range(0, N-1):
        if S[x:x+2] == 'AC':
            cnt_ac += 1
        arr_ac[x+1] = cnt_ac

    for i in range(Q):
        L, R = map(int, input().split())
        print(arr_ac[R-1] - arr_ac[L-1])


main()
### BUGGY CODE ###

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort()

cr = 0
cg = 0
p = p[:x]
q = q[:y]
for i in range(c-1, -1, -1):
    x = p.pop()
    y = q.pop()
    z = min(x, y)
    if x < y:
        q.append(y)
        if r[i] > z:
            p.insert(0, r[i])
        else:
            p.append(x)
    else:
        p.append(x)
        if r[i] > z:
            q.insert(0, r[i])
        else:
            q.append(y)
print(sum(p) + sum(q))
    
        
        



### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort()
from collections import deque
cr = 0
cg = 0
p = p[:x]
q = q[:y]
p = deque(p)
q = deque(q)
for i in range(c-1, -1, -1):
    x = p.pop()
    y = q.pop()
    z = min(x, y)
    if x < y:
        q.append(y)
        if r[i] > z:
            p.appendleft(r[i])
        else:
            p.append(x)
    else:
        p.append(x)
        if r[i] > z:
            q.appendleft(r[i])
        else:
            q.append(y)
print(sum(p) + sum(q))
### BUGGY CODE ###

while True:
    n,S = map(int, raw_input().split())
    if n == 0 and S == 0:
        break
    r = []
    for i in range(n):
        r.append(input())
    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
           if r[i] + r[j] > S:
               ans += 1
    print ans

### FIXED CODE ###

import bisect
while True:
    n,S = map(int, raw_input().split())
    if n == 0 and S == 0:
        break
    r = [input() for i in range(n)]
    ans = 0
    r.sort()
    for i in range(n):
        tmp = S - r[i] + 1
        if (tmp <= 0):
            ans += n - 1
        else:
            index = bisect.bisect_left(r, tmp)
            if (index <= i):
                ans += n - index - 1
            else:
                ans += n - index
    print ans / 2
### BUGGY CODE ###

import math
import decimal
decimal.getcontext().prec = 11

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

ans = decimal.Decimal(0)

for i in range(1, N+1):
    ans += decimal.Decimal(1 / N * (1 / 2) ** (max(math.ceil(math.log(K / i, 2)), 0)))
print(ans)

### FIXED CODE ###

import math

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

P = 0
P_log2 = 1

for i in range(1, N+1):
    if i < K:
#         T = int(math.log2(K / i)) + 1
        T = math.ceil(math.log2(K / i))
        P += 1/ N * 1 / (2 ** T)
#         print(i, T)
    else:
        P += 1 / N
# P += 1/ N * 1 / (2 ** P_log2)
            
print(P)
### BUGGY CODE ###

from itertools import permutations
N = int(input())
red = [list(map(int, input().split())) for _ in range(N)]
blue = [list(map(int, input().split())) for _ in range(N)]

def shuffle(l):
    for i in permutations(l):
        yield i

def judge(r, b):
    cnt = 0
    for i, j in zip(r, b):
        if i[0] < j[0] and i[1] < j[1]:
            cnt += 1
    return cnt

print(max([judge(red, b) for b in shuffle(blue)]))


### FIXED CODE ###

N = int(input())
red = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x:x[1], reverse=True)
blue = sorted([list(map(int, input().split())) for _ in range(N)])

cnt = 0
for i in blue:
    for j in red:
        if i[0] > j[0] and i[1] > j[1]:
            cnt += 1
            red.remove(j)
            break

print(cnt)