Harryxun/stf_run huggingface dataset:
s = input()
t = ''
if s[0] == '?':
    if s[1] == 'D':
        t = 'P'
    else:
        t = 'D'
else:
    t = s[0]
for i in range(1, len(s)):
    if s[i] == '?':
        if t[-1] == 'P':
            t += 'D'
        else:
            t += 'P'
    else:
        t += s[i]
print(t)


### FIXED CODE ###

s = input()
t = ''
for i in range(0, len(s)):
    if s[i] == '?':
        t += 'D'
    else:
        t += s[i]
print(t)
from collections import Counter
c = True
for (k, v) in Counter(input()):
  if v != 2:
    c = False
if c:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

from collections import Counter
c = True
for (k, v) in Counter(input()).items():
  if v != 2:
    c = False
if c:
  print("Yes")
else:
  print("No")
N = int(input())
for i in range(N):
  p =int(input())
  
print(int(sum(p)-max(p)/2)

### FIXED CODE ###

N = int(input())
sm,mx = 0,0
for i in range(N):
  P = int(input())
  sm += P
  mx = max(mx, P)

a = int(sm - mx / 2)
print(a)
N,M = map(int,input().split())
sum = 0
sum+=N*(N-1)/2
sum+=M*(M-1)/2
print(int(sum)

### FIXED CODE ###

N,M = map(int,input().split())
sum = 0
sum+=N*(N-1)/2
sum+=M*(M-1)/2
print(int(sum))
a, b = map(str, input().split())

A = int(a * int(b))
B = int(b + int(a))

if A > B:
  print(A)
else:
  print(B)

### FIXED CODE ###

a, b = map(str, input().split())

A = int(a * int(b))
B = int(b * int(a))

if A > B:
  print(A)
else:
  print(B)
S=map(int,input().replace(" ",""))
if S%4==0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

S=int(input().replace(" ",""))
if S%4==0:
    print("YES")
else:
    print("NO")
A,B,C,D = map(int, input().split())
lcm_number = C*D // math.gcd(C, D)  #最小公倍数
all_number = B -A + 1

answer_C = B // C - (A-1) // C
answer_D = B // D - (A-1) // D
answer_lcm = B // lcm_number - (A-1) // lcm_number

print(all_number - answer_C - answer_D + answer_lcm)

### FIXED CODE ###

import fractions

A,B,C,D = map(int, input().split())
lcm_number = C*D // fractions.gcd(C, D)
all_number = B -A + 1

answer_C = B // C - (A-1) // C
answer_D = B // D - (A-1) // D
answer_lcm = B // lcm_number - (A-1) // lcm_number

print(all_number - answer_C - answer_D + answer_lcm)
def calc_k(p, ws):
    k = 1
    s = 0
    for w in ws:
        if w > p:
            return None
        elif s + w <= p:
            s += w
        else:
            k += 1
            s = w
    return k

def search_minimum_p_internal(lp, rp, k, ws):
    "?????????P????????????????????¢?´¢??????"
    cp = (lp + rp) // 2
    k1 = calc_k(cp, ws)
    if k1 == k:
        # ???????????¨????????????????°?????????¨???k??°????????????????????????
        k2 = calc_k(cp - 1, ws)
        if k2 == None or k2 > k:
            # cp???k??°???????????????????????????p???????°??????§??????
            return cp
        else:
            # ???????°???????p????????¨??????
            return search_minimum_p_internal(lp, cp - 1, k, ws)
    elif k1 < k:
        # ???????????¨???????????????k??°???????°?????????????????????§????????????????????????????????????
        return search_minimum_p_internal(lp, cp - 1, k, ws)
    else:
        # ???????????¨???????????????k??°????????????????????????????????????????????????????¶?????????????
        return search_minimum_p_internal(cp + 1, rp, k, ws)

def search_minimum_p(k, ws):
    """
    max(P) = max(wi) * max(n)
    ????????¨???????????????1??°?????¨????????????????????????
    min(P) = max(wi)
    ?°?????????¨??????????????????????????§????????????????????????????????????
    """
    maxp = 10000 * 100000
    minp = max(ws)
    return search_minimum_p_internal(minp, maxp, k, ws)

n, k = map(int, input().split())
ws = []
for i in range(n):
    ws.append(int(input()))

print(search_minimum_p(k, ws))

### FIXED CODE ###

def calc_k(p, ws):
    k = 1
    s = 0
    for w in ws:
        if w > p:
            return None
        elif s + w <= p:
            s += w
        else:
            k += 1
            s = w
    return k

def search_minimum_p(k, ws):
    """
    ?????????P????????????????????¢?´¢??????
    max(P) = max(wi) * max(n)
    ????????¨???????????????1??°?????¨????????????????????????
    min(P) = max(wi)
    ?°?????????¨??????????????????????????§????????????????????????????????????
    """
    lp = max(ws)
    rp = 10000 * 100000

    while lp <= rp:
        cp = (lp + rp) // 2
        k1 = calc_k(cp, ws)
        if k1 <= k:
            # ???????????¨???????????????k??°??\????????????????????§??????
            k2 = calc_k(cp - 1, ws)
            if k2 == None or k2 > k:
                # cp???k??°???????????????????????????p???????°??????§??????
                return cp
            else:
                # ???????°???????p????????¨??????
                rp = cp - 1
        else:
            # ???????????¨???????????????k??°????????????????????????????????????????????????????¶?????????????
            lp = cp + 1

    return None

n, k = map(int, input().split())
ws = []
for i in range(n):
    ws.append(int(input()))

print(search_minimum_p(k, ws))
n=int(input())
a=[int(i) for i in input().split()]
ans=0
a.sort()
a.reverse()
if n%2==0:
    p=n//2
else:
    p=n//2+1
c=1
lp=[]
lm=[]
for i in a:
    if i>0 and c<=p:
        ans+=i
        lp.append(i)
    else:
        ans-=i
        lm.append(i)
    c+=1
print(ans)
llp=len(lp)
llm=len(lm)
q=[]
i=0
j=0
k=0
o=0
while o==0:
    if llp>llm:
        if lp!=[] and lm!=[]:
            lm.append(-lp[0]+lm[0])
            print(lm[0],lp[0])
            del lp[0]
            del lm[0]
        elif lm!=[]:
            print(lm[0],lm[-1])
            del lm[0]
            del lm[-1]
        else:
            o=1
    else:
        if lp!=[] and lm!=[]:
            lp.append(lp[0]-lm[0])
            print(lp[0],lm[0])
            del lp[0]
            del lm[0]
        elif lp!=[]:
            print(lp[0],lp[-1])
            del lp[0]
            del lp[-1]
        else:
            o=1
            
            
        
        
        
    
        





 

### FIXED CODE ###

n=int(input())
a=[int(j) for j in input().split()]
a.sort()
ans=[]
p=a[0]
q=a[-1]
for i in a[1:-1]:
    if i<0:
        ans.append([q,i])
        q-=i
    else:
        ans.append([p,i])
        p-=i
ans.append([q,p])
print(q-p)
for i,j in ans:
    print(i,j)
import collections
counter = collections.Counter()

for i in input():
  counter[i] += 1
  
if len([i for i in counter.values() if i >= 1]) == 3:
  print*"Yes")
else:
  print("No")

### FIXED CODE ###

import collections
counter = collections.Counter()

for i in input():
  	counter[i] += 1

if len([i for i in counter.values() if i >= 1]) == 3:
	print("Yes")
else:
    print("No")
s = input()
pr = s[0]
cnt = 0
i = 0
while i < len(s)-1:
    if len(pr) == 1:
        if s[i+1] == pr:
            if i+2 < len(s)-1:
                cnt += 1
                pr = s[i+1:i+3]
                i += 2
            else:
                break
        else:
            cnt += 1
            pr = s[i+1]
            i += 1
    else:
        cnt += 1
        pr = s[i+2]
        i += 1
print(cnt+1)

### FIXED CODE ###

def calc(pr, s):
    cnt = 0
    i = 0
    while i < len(s)-1:
        if len(pr) == 1:
            if s[i+1] == pr:
                if i+2 < len(s):
                    cnt += 1
                    pr = s[i+1:i+3]
                    i += 1
                else:
                    break
            else:
                cnt += 1
                pr = s[i+1]
                i += 1
        else:
            if i+2 < len(s):
                cnt += 1
                pr = s[i+2]
                i += 2
            else:
                break
    return cnt+1

s = input()
pr1 = s[0]
pr2 = s[:2]
print(max(calc(pr1, s), calc(pr2, s)))
L,R = map(int,input().split())

for i in range(1,10**6):
    if i * 2019 >= L and i*2019 <= R:
        print(0)
        exit()

ans = 10**20

for i in range(L,min(L+2019,R+1)):
    for j in range(L,min(L+2019,R+1)):
        if i >= j:
            continue
        ans = min(ans,(i*j)%2019)
￥for i in range(max(L,R-2019),R+1):
    for j in range(max(L,R-2019),R+1):
        if i >= j:
            continue
        ans = min(ans,(i*j)%2019)
print(ans)


### FIXED CODE ###

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

for i in range(1,10**6):
    if i * 2019 >= L and i*2019 <= R:
        print(0)
        exit()

ans = 10**20

for i in range(L,min(L+2019,R+1)):
    for j in range(L,min(L+2019,R+1)):
        if i >= j:
            continue
        ans = min(ans,(i*j)%2019)
for i in range(max(L,R-2019),R+1):
    for j in range(max(L,R-2019),R+1):
        if i >= j:
            continue
        ans = min(ans,(i*j)%2019)
print(ans)
n = input
ans = ''
for i in range(len(n)):
    if n[i] == '1':
        ans += '9'
    else :
        ans += '1'
print(ans)

### FIXED CODE ###

n = input()
ans = ''
for i in range(3):
    if n[i] == '1':
        ans += '9'
    else :
        ans += '1'
print(ans)
n = int(input())

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


from functools import lru_cache
import sys
if n == 2:
    print(max(a))
    sys.exit()


@lru_cache(maxsize=100000)
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def gcd_list(li):
    g = gcd(li[0], li[1])
    for i in range(2, n):
        g = gcd(g, a[i])
    return g


def gcd_list_2(li):
    g = gcd(li[0], li[1])
    if g == 1:
        return max(gcd_list([li[0]] + li[2:]), gcd_list(li[1:]))
    for i in range(2, n):
        if gcd(g, a[i]) == 1:
            return gcd_list([g] + li[i + 1:])
        else:
            g = gcd(g, a[i])
    return g


def max_gcd(a):
    g = gcd_list(a)
    a = [a[i]//g for i in range(n)]

    m = gcd_list_2(a)
    print(g * m)


max_gcd(a)

### FIXED CODE ###


n = int(input())

a = list(map(int, input().split()))
a.sort(reverse=True)


from functools import lru_cache
import sys
if n == 2:
    print(max(a))
    sys.exit()


@lru_cache(maxsize=100000)
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


def gcd_list(li):
    if len(li) == 1:
        return li[0]
    g = gcd(li[0], li[1])
    for i in range(2, len(li)):
        g = gcd(g, li[i])
    return g


def gcd_list_2(li):
    g = gcd(li[0], li[1])
    if g == 1:
        return max(gcd_list([li[0]] + li[2:]), gcd_list(li[1:]))
    for i in range(2, n):
        if gcd(g, li[i]) == 1:
            if i == n - 1:
                return gcd_list(li[:i])
            gg = gcd_list(li[i+1:])
            bb = [gcd(li[x], gg) for x in range(i+1)]
            bb.sort()
            return bb[1]
        else:
            g = gcd(g, li[i])
    return g


def max_gcd(a):
    g = gcd_list(a)
    a = [a[i]//g for i in range(n)]
    m = gcd_list_2(a)
    print(g * m)


max_gcd(a)
a,b=input().split()
b = b*100
print(a*b//100)

### FIXED CODE ###

from decimal import Decimal
a,b=map(Decimal, input().split())
print(int(a*b))
n = int(input())
h = []

for i in range(n):
	h.append(int(input()))

count = 0
count_list = [0]

for i in range(n-1):
	if(h[i+1] <= h[i]):
		count += 1
		count_list.append(count)
	else:
		count = 0

print(max(count_list))

### FIXED CODE ###

import sys

n = int(input())
a = []
b = input().split(" ")
for i in range(n):
	a.append(int(b[i]))

if n == 1:
	print(0)
	sys.exit()

mx = 0
cnt = 0
for i in range(n-2, -1, -1):
	if a[i] >= a[i+1]:
		cnt += 1
		mx = max(mx, cnt)
	else:
		cnt = 0

print(mx)
import sys

if __name__ == '__main__':
  args = sys.argv
  ret="No"
  
  if (args[1] == args[2] || args[2] == args[3] || args[1] == args[3]):
    ret="Yes"
    
  print(ret)

### FIXED CODE ###

import sys
 
if __name__ == '__main__':
  args = input().split()
  ret="No"
  if ((args[0] == args[1] or args[0] == args[2] or args[1] == args[2]) and (args[0] != args[1] or args[1] != args[2])):
    ret="Yes"
    
  print(ret)
from math import gcd

n = int(input())
a = [int(i) for i in input().split()]

l = [0 for i in range(n)]
for i in range(1, n):
    l[i] = gcd(a[i-1], l[i-1])

r = [0 for i in range(n)]
for i in range(n-1)[::-1]:
    r[i] = gcd(a[i+1], r[i+1])

m = [gcd(l[i], r[i]) for i in range(n)]
print(max(m))


### FIXED CODE ###

def gcd(a, b):
    if a == 0:
        return b
    if b == 0:
        return a
    if a < b:
        return gcd(b, a)
    r = a % b
    return b if r == 0 else gcd(b, r)


n = int(input())
a = [int(i) for i in input().split()]

l = [0 for i in range(n)]
for i in range(1, n):
    l[i] = gcd(a[i-1], l[i-1])

r = [0 for i in range(n)]
for i in range(n-1)[::-1]:
    r[i] = gcd(a[i+1], r[i+1])

m = [gcd(l[i], r[i]) for i in range(n)]
print(max(m))
def resolve():
    a,b,k=map(int,input().split())
    l=list(range(a,b+1))
    ans=l[:k]
    ans+=l[-k:]
    answer=sorted(list(set(ans)))
    for i in answer:
        print(i)
resolve()

### FIXED CODE ###

def resolve():
    a,b,k=map(int,input().split())
    realk=min(b-a+1,k)
    ans=list(range(a,a+realk))
    ans+=list(range(b-realk+1,b+1))
    answer=sorted(list(set(ans)))
    for i in answer:
        print(i)
    

resolve()
from collections import Counter, defaultdict
H, W = map(int, input().split(' '))
d = defaultdict(int)
for i in range(H):
    for k, v in Counter(input()).items():
        d[k] += v
if H % 2 == 0 and W % 2 == 0:
    for i in d.values():
        if i % 4 != 0:
            print('No')
            exit()
    print('Yes')
elif H % 2 == 0 or W % 2 == 0:
    raise TypeError
    cnt = H//2 if not H % 2 else W//2
    for i in d.values():
        if i % 4 == 0:
            continue
        elif i % 2 == 0:
            cnt -= 1
            if cnt >= 0:
                continue
        print('No')
        exit()
    print('Yes')
else:
    raise TypeError
    odd = 1
    cnt = H+W-1
    for i in d.values():
        if i % 2 != 0 and odd:
            odd -=1
            continue
        elif i % 4 == 0:
            continue
        elif i % 2 == 0 and cnt:
            cnt -= 1
            continue
        else:
            print('No')
            exit()
    print('Yes')

### FIXED CODE ###

from collections import Counter, defaultdict
H, W = map(int, input().split(' '))
d = defaultdict(int)
for i in range(H):
    for k, v in Counter(input()).items():
        d[k] += v
if H % 2 == 0 and W % 2 == 0:
    for i in d.values():
        if i % 4 != 0:
            print('No')
            exit()
    print('Yes')
elif H % 2 == 0 or W % 2 == 0:
    cnt = H//2 if not H % 2 else W//2
    for i in d.values():
        if i % 4 == 0:
            continue
        elif i % 2 == 0:
            cnt -= 1
            if cnt >= 0:
                continue
        print('No')
        exit()
    print('Yes')
else:
    odd = 1
    cnt = (H+W-2)//2
    for i in d.values():
        if i % 2 != 0 and odd:
            odd -= 1
            continue
        elif i % 4 == 0:
            continue
        elif i % 2 == 0 and cnt:
            cnt -= 1
            continue
        else:
            print('No')
            exit()
    print('Yes')
import math

def kaijo(n):
    return math.factorial(n)

INF = 10 ** 9 + 7
N = int(input())
x = list(map(int, input().split()))
k = kaijo(N - 1)
tmp = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        tmp += ((x[j] - x[i]) / (N - 1 - j + 1)) % INF
    tmp += ((x[-1] - x[i]) / 2) % INF
tmp += ((x[-1] - x[-2])) % INF
ans = int(tmp * k)
ans %= INF
print(ans)

### FIXED CODE ###

import math
N = int(input())
x = list(map(int, input().split()))
kyori = [x[i + 1] - x[i] for i in range(N - 1)]
MOD = 10 ** 9 + 7
kai = [0] * (N + 1)
kai[0] = 1
for i in range(1, N + 1):
    kai[i] = (kai[i - 1] * i) % MOD
c = [0] * N
c[0] = 0
for i in range(1, N):
    c[i] = ((kai[N - 1] * pow(i, MOD - 2, MOD) % MOD) + c[i - 1]) % MOD
ans = 0
for i in range(N - 1):
    ans = (ans + kyori[i] * c[i + 1] % MOD) % MOD

print(ans)
a, b = map[int, input().split()]
print (a*b, 2*(a+b))


### FIXED CODE ###

a, b = map(int, input().split())
print (a*b, 2*(a+b))
N,M=map(int,input().split())
a=[]
for i in range(0,M):
    a.append(int(input()))
ans=1
s=[-1]*(N+1)
s[0]=1
def dp(n):
    if n==0:
        return 1
    elif n==1:
        return 0 if 1 in a else 1
    if s[n-1]!=-1:
        c=s[n-1]
    elif n-1 in a:
        s[n-1]=0
        c=0
    else:
        c=dp(n-1)
        s[n-1]=c
    if s[n-2]!=-1:
        b=s[n-2]
    elif n-2 in a:
        s[n-2]=0
        b=0
    else:
        b=dp(n-2)
        s[n-2]=b
    return c+b
print(dp(N)%1000000007)

### FIXED CODE ###

import sys #追加
sys.setrecursionlimit(50000000) #追加
N,M=map(int,input().split())
a=[]
for i in range(0,M):
    a.append(int(input()))
a=set(a)
if M==0:
    a=[-1]
ans=1
s=[-1]*(N+1)
s[0]=1
def dp(n):
    if n==0:
        return 1
    elif n==1:
        return 0 if 1 in a else 1
    if s[n-1]!=-1:
        c=s[n-1]
    elif n-1 in a:
        s[n-1]=0
        c=0
    else:
        c=dp(n-1)%1000000007
        s[n-1]=c
    if s[n-2]!=-1:
        b=s[n-2]
    elif n-2 in a:
        s[n-2]=0
        b=0
    else:
        b=dp(n-2)%1000000007
        s[n-2]=b
    return (c+b)%1000000007
print(dp(N)%1000000007)
N = int(input())
A = [int(i) for i in input().split()]

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
if N<=2:
    print(max(A))
else:
    gcds = []
    for n in range(N):
        if n == 0:
            lgcd = None
        else:
            lgcd = A[0]
            for i in range(n):
                lgcd = gcd(lgcd,A[i])
        if n == N-1:
            rgcd = None
        else:
            rgcd = A[n+1]
            for i in range(n+1,N):
                rgcd = gcd(rgcd,A[i])
        if lgcd == None:
            gcds.append(rgcd)
        elif rgcd == None:
            gcds.append(lgcd)
        else:
            gcds.append(gcd(lgcd,rgcd))
print(max(gcds))

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a  
lgcds = [A[0]]
rgcds = [A[N-1]]
for n in range(N-2):
    lgcds.append(gcd(lgcds[-1],A[n+1]))
    rgcds.append(gcd(rgcds[-1],A[-2-n]))
gcds = [lgcds[-1],rgcds[-1]]
for i in range(N-2):
    gcds.append(gcd(lgcds[i],rgcds[-2-i]))
print(max(gcds))
a,b=map(int, input().split())

count=0
tmp=0

for i in range(1,21):
    if (a-1)*i+1 >= b:
        print(i)
        break


### FIXED CODE ###

s=input()
t=input()

count = 0

for s,t in zip(s,t):
    if s==t: count+=1

print(count)
N = int(input())
A = [int(input()) for _ in range(N)]

m1, m2 = sorted(A, reversed=True)[0:2]
for a in A:
    print(m2 if a == m1 else m1)

### FIXED CODE ###

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

mls = [-1 for _ in range(N+1)]
for i, a in enumerate(A, 1):
    mls[i] = max(mls[i-1], a)

mrs = [-1 for _ in range(N+1)]
for i, a in enumerate(A[::-1], 1):
    mrs[i] = max(mrs[i-1], a)
mrs = mrs[::-1]

for i in range(N):
    print(max(mls[i], mrs[i+1]))
s,t = input().split())
a,b = map(int,input().split())
u = input()

if s == u:
    print(a -1,b)
else:
    print(a,b-1)

### FIXED CODE ###

s,t = input().split()
a,b = map(int,input().split())
u = input()

if s == u:
    print(a -1,b)
else:
    print(a,b-1)
N = input()
a = [int(input()) for _ in range(N)]
print(sum(a[::2]) - sum(a[1::2]))

### FIXED CODE ###

N = input()
a = sorted(list(map(int, input().split())), reverse=True)
print(sum(a[::2]) - sum(a[1::2]))
#!/usr/bin/env python3
from decimal import Decimal

n = int(input())

arg = list(map(Decimal, input().split()))
ans = Decimal("1")

for m in arg:
    ans = ans * m

if ans > Decimal("1000000000000000000"):
    ans = -1
    
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
n = int(input())

arg = list(map(int, input().split()))
ans = 1

if 0 in arg:
    ans = 0
else:
    for m in arg:
        ans *= m

        if ans > 1000000000000000000:
            ans = -1
            break

print(ans)
s = input()
if((s[0]==s[1] and s[2]==s[3] and s[0]!=s[2]) or (s[0]==s[2] and s[1] ==s[3] and s[0]!=s[1])
   and (s[0]===s[3] and s[1]==s[2] and s[0]!=s[1])):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s = input()
if((s[0]==s[1] and s[2]==s[3] and s[0]!=s[2]) or (s[0]==s[2] and s[1] ==s[3] and s[0]!=s[1])
   or (s[0]==s[3] and s[1]==s[2] and s[0]!=s[1])):
  print("Yes")
else:
  print("No")
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[0], reverse=True)
num.sort(key=lambda x: x[1])
dp = ["" for i in range(N+1)]
ans = 0
for x in num:
    tmp = set()

    for i in range(1, N+1-x[1]):
        for n, k in num:
            if i - k in tmp:
                dp[i] = dp[i-k]+str(n)
                tmp.add(i)
                break
            else:
                if i == k:
                    dp[i] = str(n)
                    tmp.add(k)
                    break
    tmp2 = list(dp[N-x[1]])
    tmp2.append(str(x[0]))
    tmp2.sort(reverse=True)
    ans = max(int("".join(map(str, tmp2))), ans)
print(ans)


### FIXED CODE ###

import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[0], reverse=True)
num.sort(key=lambda x: x[1])
dp = [0 for i in range(N+1)]
ans = 0
tmp = set()
tmp.add(0)
for i in range(1, N+1):
    for n, k in num:
        if i - k in tmp:
            dp[i] = 1 + dp[i-k]
            tmp.add(i)
            break


num.sort(reverse=True)
tmp = N
ans = []
for i in reversed(range(1, dp[N])):
    for n, k in num:
        if dp[tmp - k] == i:
            ans.append(n)
            tmp -= k
            break
for n, k in num:
    if k == tmp:
        ans.append(n)
        break

ans.sort(reverse=True)
ans = "".join(map(str, ans))
print(ans)
h, w = (list)(map(int, input().split()))
l = [[lin for lin in input()] for _ in range(h)]

gri = [[0 for i in range(w+2)] for _ in range(h+2)]
for i in range(h+2):
    for j in range(w+2):
        if i == 0 or i == h+1 or j == 0 or j == w+1:
            gri[i][j] = '.'
        else:
            gri[i][j] = l[i-1][j-1]


for i in range(1, h+1):
    for j in range(1, w+1):
        if gri[i][j] == '#':
            if gri[i-1][j] == '.' and gri[i+1][j] == '.' and gri[i][j-1] == '.' and gri[i][j+1] == '.':
                print("No")
                exit(1)

print("Yes")


### FIXED CODE ###

h, w = (list)(map(int, input().split()))
l = [[lin for lin in input()] for _ in range(h)]

gri = [['.' for i in range(w+2)] for _ in range(h+2)]
for i in range(1, h+1):
    for j in range(1, w+1):
        gri[i][j] = l[i-1][j-1]

flag = 1
for i in range(1, h+1):
    for j in range(1, w+1):
        if gri[i][j] == '#':
            if gri[i-1][j] == '.' and gri[i+1][j] == '.' and gri[i][j-1] == '.' and gri[i][j+1] == '.':
                flag = 0
if flag == 1:
    print("Yes")
else:
    print("No")
N = int(input())

red_points = [[int(i) for i in input().split()] for j in range(N)]

blue_points = [[int(i) for i in input().split()] for j in range(N)]

red_points.sort()
blue_points.sort()
count = 0
distance = 9999
for blue_point in blue_points:
    for red_point in red_points:
        if (blue_point[0] > red_point[0]) and (blue_point[1] > red_point[1]):
            if blue_point[1] - red_point[1] < distance:
                distance = blue_point[1] - red_point[1]
                tmp = red_point
    if tmp in red_points:
        red_points.remove(tmp)
        tmp.clear()
        count = count + 1
    distance = 9999
print(count)


### FIXED CODE ###

N = int(input())

red_points = [[int(i) for i in input().split()] for j in range(N)]

blue_points = [[int(i) for i in input().split()] for j in range(N)]

red_points.sort()
blue_points.sort()
count = 0
distance = 9999
for blue_point in blue_points:
    tmp = [i for i in red_points if blue_point[0] > i[0] and blue_point[1] > i[1]]
    if tmp:
        for j in tmp:
            if (blue_point[1] - j[1]) < distance:
                distance = blue_point[1] - j[1]
                min_red = j
        count = count + 1
        red_points.remove(min_red)
        distance = 9999

print(count)