Problem:


マトリョーシカ

マトリョーシカとは女性像をかたどった木製の人形で、ロシアの代表的な民芸品です。マトリョーシカは、大きな人形の中にそれより小さな人形が入っている入れ子構造になっており、大きさの異なる複数の人形で構成されています。このような入れ子構造にするため、各人形の胴体は上下で分割できる筒状の構造になっています。マトリョーシカは職人の手で手作りされるため、一つ一つの人形は世界に一つしかない非常に貴重なものになります。

兄弟である一郎君と次郎君は、マトリョーシカで遊ぶのが大好きで、各自がそれぞれ1組のマトリョーシカを持っていました。一郎君のマトリョーシカは n 個の人形から構成されており、次郎君のマトリョーシカは m 個の人形から構成されています。

ある日、好奇心が旺盛な一郎君は、これら2組のマトリョーシカに含まれる人形たちを組み合わせて、より多くの人形を含む新たなマトリョーシカを作れないかと考えました。つまり、n + m 個の人形を使い、k 個の人形からなる１組のマトリョーシカを作ることを試みたのです。n と m の大きい方よりも k を大きくすることができれば、一郎君の目的は達成されます。

兄弟は2人仲良く、どのように人形を組み合わせれば k の値を最大にできるかを考えました。しかし、幼い2人にとってこの問題はあまりにも難しいので、年上のあなたはプログラムを作成して弟たちを助けることにしました。

一郎君と次郎君のマトリョーシカの人形の情報を入力とし、新たなマトリョーシカが含む人形の数 k を出力するプログラムを作成して下さい。入力される人形に大きさが同じものは存在しません。また、人形を高さ h 半径 r の円柱とみなした場合、高さh、半径 r の人形が含むことのできる人形は x < h  かつ y < r を満たす高さ x 半径 y の人形です。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。各データセットは以下の形式で与えられます。

n
h1 r1
h2 r2
:
hn rn
m
h1 r1
h2 r2
:
hm rm

１行目に一郎君のマトリョーシカの人形の数 n (n ≤ 100)、続く n 行に一郎君の第 i の人形の高さ hi と半径 ri (hi, ri < 1000) が与えられます。

続く行に二郎君のマトリョーシカの人形の数 m (m ≤ 100)、続く m 行に二郎君の第 i の人形の高さ hi と半径 ri (hi, ri < 1000) が与えられます。

データセットの数は 20 を越えない。

Output

入力データセットごとに新たなマトリョーシカが含む人形の数 k を出力します。

Sample Input

6
1 1
4 3
6 5
8 6
10 10
14 14
5
2 2
5 4
6 6
9 8
15 10
4
1 1
4 3
6 5
8 6
3
2 2
5 4
6 6
4
1 1
4 3
6 5
8 6
4
10 10
12 11
18 15
24 20
0

Output for the Sample Input

9
6
8



Sample input:
6
1 1
4 3
6 5
8 6
10 10
14 14
5
2 2
5 4
6 6
9 8
15 10
4
1 1
4 3
6 5
8 6
3
2 2
5 4
6 6
4
1 1
4 3
6 5
8 6
4
10 10
12 11
18 15
24 20
0


Sample output:
9
6
8

Submission status: Wrong Answer

Solution code:
def f(f1, f2):
    res = 1
    c = 0
    i = 0
    while c < len(L)-1:
        if L[i][f1] > L[i+1][f1] and L[i][f2] > L[i+1][f2]:
            res += 1
            i += 1
        else:
            del L[i+1]
        c += 1
    return res

while True:
    n = input()
    if n == 0: break
    L = [map(int, raw_input().split()) for i in range(n)]
    for i in range(input()):
        L.append(map(int, raw_input().split()))
    else:
        h = 0
        r = 1
        L.sort(key=lambda x: (x[h], x[r]), reverse=True)
        res1 = f(h, r)
        L.sort(key=lambda x: (x[r], x[h]), reverse=True)
        res2 = f(r, h)
        if res2 < res1:
            print res1
        else:
            print res2

Submission status: Wrong Answer

Solution code:
def f(f1, f2):
    res = 1
    c = 0
    i = 0
    while c < len(L)-1:
        if L[i][f1] > L[i+1][f1] and L[i][f2] > L[i+1][f2]:
            res += 1
            i += 1
        else:
            del L[i+1]
        c += 1
    return res

while True:
    n = input()
    if n == 0: break
    L = [map(int, raw_input().split()) for i in range(n)]
    for i in range(input()):
        L.append(map(int, raw_input().split()))
    else:
        h = 0
        r = 1
        L.sort(key=lambda x: x[h], reverse=True)
        L.sort(key=lambda x: x[r], reverse=True)
        res1 = f(h, r)
        L.sort(key=lambda x: x[r], reverse=True)
        L.sort(key=lambda x: x[h], reverse=True)
        res2 = f(r, h)
        if res2 < res1:
            print res1
        else:
            print res2

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

def f(f1, f2):
    res = 1
    c = 0
    i = 0
    while c < len(L)-1:
        if L[i][f1] > L[i+1][f1] and L[i][f2] > L[i+1][f2]:
            res += 1
            i += 1
        else:
            del L[i+1]
        c += 1
    return res

while True:
    n = input()
    if n == 0: break
    L = [map(int, raw_input().split()) for i in range(n)]
    for i in range(input()):
        L.append(map(int, raw_input().split()))
    else:
        h = 0
        r = 1
        L.sort(key=itemgetter(0,1), reverse=True)
        res1 = f(h, r)
        L.sort(key=itemgetter(1,0), reverse=True)
        res2 = f(r, h)
        if res2 < res1:
            print res1
        else:
            print res2

Submission status: Wrong Answer

Solution code:
import copy
from operator import itemgetter

def f(f1, f2):
    res = 1
    c = 0
    i = 0
    _L = copy.deepcopy(L)
    while c < len(_L)-1:
        if _L[i][f1] > _L[i+1][f1] and _L[i][f2] > _L[i+1][f2]:
            res += 1
            i += 1
        else:
            del _L[i+1]
        c += 1
    return res

while True:
    n = input()
    if n == 0: break
    L = [map(int, raw_input().split()) for i in range(n)]
    for i in range(input()):
        L.append(map(int, raw_input().split()))
    else:
        h = 0
        r = 1
        L.sort(key=itemgetter(0,1), reverse=True)
        res1 = f(h, r)
        L.sort(key=itemgetter(1,0), reverse=True)
        res2 = f(r, h)
        if res2 < res1:
            print res1
        else:
            print res2

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-

def solve(N, M, H1, R1, H2, R2):
    h = 0
    r = 0
    i1 = 0
    i2 = 0
    cnt = 0
    while i1 < N or i2 < M:
        print i1, i2
        if i2 >= M:
            if h < H1[i1] and r < R1[i1]:
                r = R1[i1]
                h = H1[i1]
                i1 += 1
                cnt += 1
            else:
                i1 += 1
        elif i1 >= N:
            if h < H2[i2] and r < R2[i2]:
                r = R2[i2]
                h = H2[i2]
                i2 += 1
                cnt += 1
            else:
                i2 += 1
        else:
            if H1[i1] == H2[i2]:
                r = min(R1[i1],R2[i2])
                h = H1[i1]
                i1 += 1
                i2 += 1
                cnt += 1
            elif R1[i1] == R2[i2]:
                r = R1[i1]
                h = min(H1[i1],H2[i2])
                i1 += 1
                i2 += 1
                cnt += 1
            elif H1[i1]+R1[i1] <= H2[i2]+R2[i2]:
                if h < H1[i1] and r < R1[i1]:
                    r = R1[i1]
                    h = H1[i1]
                    i1 += 1
                    cnt += 1
                else:
                    i1 += 1
            elif H1[i1]+R1[i1] > H2[i2]+R2[i2]:
                if h < H2[i2] and r < R2[i2]:
                    r = R2[i2]
                    h = H2[i2]
                    i2 += 1
                    cnt += 1
                else:
                    i2 += 1
    print cnt

if __name__ == "__main__":
    import sys

    while True:
        N = int(raw_input())
        if N == 0:
            sys.exit()
        H1 = [0] * N
        R1 = [0] * N
        for i in xrange(N):
            H1[i], R1[i] = map(int, raw_input().split())
        M = int(raw_input())
        H2 = [0] * M
        R2 = [0] * M
        for i in xrange(M):
            H2[i], R2[i] = map(int, raw_input().split())

        solve(N, M, H1, R1, H2, R2)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-

def solve(N, M, H1, R1, H2, R2):
    h = 0
    r = 0
    i1 = 0
    i2 = 0
    cnt = 0
    while i1 < N or i2 < M:
        if i2 >= M:
            if h < H1[i1] and r < R1[i1]:
                r = R1[i1]
                h = H1[i1]
                i1 += 1
                cnt += 1
            else:
                i1 += 1
        elif i1 >= N:
            if h < H2[i2] and r < R2[i2]:
                r = R2[i2]
                h = H2[i2]
                i2 += 1
                cnt += 1
            else:
                i2 += 1
        else:
            if H1[i1] == H2[i2]:
                r = min(R1[i1],R2[i2])
                h = H1[i1]
                i1 += 1
                i2 += 1
                cnt += 1
            elif R1[i1] == R2[i2]:
                r = R1[i1]
                h = min(H1[i1],H2[i2])
                i1 += 1
                i2 += 1
                cnt += 1
            elif H1[i1]+R1[i1] <= H2[i2]+R2[i2]:
                if h < H1[i1] and r < R1[i1]:
                    r = R1[i1]
                    h = H1[i1]
                    i1 += 1
                    cnt += 1
                else:
                    i1 += 1
            elif H1[i1]+R1[i1] > H2[i2]+R2[i2]:
                if h < H2[i2] and r < R2[i2]:
                    r = R2[i2]
                    h = H2[i2]
                    i2 += 1
                    cnt += 1
                else:
                    i2 += 1
    print cnt

if __name__ == "__main__":
    import sys

    while True:
        N = int(raw_input())
        if N == 0:
            sys.exit()
        H1 = [0] * N
        R1 = [0] * N
        for i in xrange(N):
            H1[i], R1[i] = map(int, raw_input().split())
        M = int(raw_input())
        H2 = [0] * M
        R2 = [0] * M
        for i in xrange(M):
            H2[i], R2[i] = map(int, raw_input().split())

        solve(N, M, H1, R1, H2, R2)

Submission status: Wrong Answer

Solution code:
while True:
  n = int(input())
  if n == 0:
    break
  hr_lst = []
  for _ in range(n):
    h, r = map(int, input().split())
    hr_lst.append((h, r))
  
  m = int(input())
  for _ in range(m):
    h, r = map(int, input().split())
    hr_lst.append((h, r))

  hr_lst.sort()
  r_lst = [r for _, r in hr_lst]
  
  """
  dp[y] ... 最大yまでの最大入れ子数
  dp[y] = max(dp[y], dp[rlst[x] - 1] + 1)
  """
  dp = [0] * 1001
  for x in range(len(r_lst)):
    vx = r_lst[x]
    for y in range(vx, 1001):
      dp[y] = max(dp[y], dp[vx - 1] + 1)
  print(dp[1000])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-

def solve(N, M, H1, R1, H2, R2):
    h = 0
    r = 0
    i1 = 0
    i2 = 0
    cnt = 0
    while i1 < N or i2 < M:
        if i1 < N and i2 < M:
            if H1[i1] == H2[i2] or R1[i1] == R2[i2]:
                if H1[i1] == H2[i2]:
                    if R1[i1] <= R2[i2]:
                        r = R1[i1]
                        h = H1[i1]
                        i1 += 1
                        i2 += 1
                        cnt += 1
                    else:
                        r = R2[i2]
                        h = H2[i2]
                        i1 += 1
                        i2 += 1
                        cnt += 1
                else:
                    if H1[i1] <= H2[i2]:
                        r = R1[i1]
                        h = H1[i1]
                        i1 += 1
                        i2 += 1
                        cnt += 1
                    else:
                        h = H2[i2]
                        r = R2[i2]
                        i1 += 1
                        i2 += 1
                        cnt += 1
            elif H1[i1] < H2[i2] and R1[i1] < R2[i2]:
                if h < H1[i1] and r < R1[i1]:
                    r = R1[i1]
                    h = H1[i1]
                    i1 += 1
                    cnt += 1
                else:
                    i1 += 1
            elif H1[i1] > H2[i2] and R1[i1] > R2[i2]:
                if h < H2[i2] and r < R2[i2]:
                    r = R2[i2]
                    h = H2[i2]
                    i2 += 1
                    cnt += 1
                else:
                    i2 += 1
        elif i1 < N:
            if h < H1[i1] and r < R1[i1]:
                r = R1[i1]
                h = H1[i1]
                i1 += 1
                cnt += 1
            else:
                i1 += 1
        elif i2 < M:
            if h < H2[i2] and r < R2[i2]:
                r = R2[i2]
                h = H2[i2]
                i2 += 1
                cnt += 1
            else:
                i2 += 1

    print cnt



if __name__ == "__main__":
    import sys

    while True:
        N = int(raw_input())
        if N == 0:
            sys.exit()
        H1 = [0] * N
        R1 = [0] * N
        for i in xrange(N):
            H1[i], R1[i] = map(int, raw_input().split())
        M = int(raw_input())
        H2 = [0] * M
        R2 = [0] * M
        for i in xrange(M):
            H2[i], R2[i] = map(int, raw_input().split())
        solve(N, M, H1, R1, H2, R2)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-

def solve(N, M, H1, R1, H2, R2):
    h = 0
    r = 0
    i1 = 0
    i2 = 0
    cnt = 0
    while i1 < N or i2 < M:
        if i1 < N and i2 < M:
            if H1[i1] == H2[i2] or R1[i1] == R2[i2]:
                if H1[i1] == H2[i2]:
                    if R1[i1] <= R2[i2]:
                        r = R1[i1]
                        h = H1[i1]
                        i1 += 1
                        i2 += 1
                        cnt += 1
                    else:
                        r = R2[i2]
                        h = H2[i2]
                        i1 += 1
                        i2 += 1
                        cnt += 1
                else:
                    if H1[i1] <= H2[i2]:
                        r = R1[i1]
                        h = H1[i1]
                        i1 += 1
                        i2 += 1
                        cnt += 1
                    else:
                        h = H2[i2]
                        r = R2[i2]
                        i1 += 1
                        i2 += 1
                        cnt += 1
            elif H1[i1] < H2[i2] and R1[i1] < R2[i2]:
                if h < H1[i1] and r < R1[i1]:
                    r = R1[i1]
                    h = H1[i1]
                    i1 += 1
                    cnt += 1
                else:
                    i1 += 1
            elif H1[i1] > H2[i2] and R1[i1] > R2[i2]:
                if h < H2[i2] and r < R2[i2]:
                    r = R2[i2]
                    h = H2[i2]
                    i2 += 1
                    cnt += 1
                else:
                    i2 += 1
        elif i1 < N:
            if h < H1[i1] and r < R1[i1]:
                r = R1[i1]
                h = H1[i1]
                i1 += 1
                cnt += 1
            else:
                i1 += 1
        elif i2 < M:
            if h < H2[i2] and r < R2[i2]:
                r = R2[i2]
                h = H2[i2]
                i2 += 1
                cnt += 1
            else:
                i2 += 1
        else:
            raise ValueError(",".join(H1)+ "+" +",".join(H2)+"+"+",".join(R1)+"+"+",".join(R2))

    print cnt



if __name__ == "__main__":
    import sys

    while True:
        N = int(raw_input())
        if N == 0:
            sys.exit()
        H1 = [0] * N
        R1 = [0] * N
        for i in xrange(N):
            H1[i], R1[i] = map(int, raw_input().split())
        M = int(raw_input())
        H2 = [0] * M
        R2 = [0] * M
        for i in xrange(M):
            H2[i], R2[i] = map(int, raw_input().split())
        solve(N, M, H1, R1, H2, R2)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-

def solve(N, M, H1, R1, H2, R2):
    h = 0
    r = 0
    i1 = 0
    i2 = 0
    cnt = 0
    while i1 < N or i2 < M:
        if i2 >= M:
            if h < H1[i1] and r < R1[i1]:
                r = R1[i1]
                h = H1[i1]
                i1 += 1
                cnt += 1
            else:
                i1 += 1
        elif i1 >= N:
            if h < H2[i2] and r < R2[i2]:
                r = R2[i2]
                h = H2[i2]
                i2 += 1
                cnt += 1
            else:
                i2 += 1
        else:
            if H1[i1] == H2[i2]:
                r = min(R1[i1],R2[i2])
                h = H1[i1]
                i1 += 1
                i2 += 1
                cnt += 1
            elif R1[i1] == R2[i2]:
                r = R1[i1]
                h = min(H1[i1],H2[i2])
                i1 += 1
                i2 += 1
                cnt += 1
            elif H1[i1] < H2[i2] and R1[i1] < R2[i2]:
                if h < H1[i1] and r < R1[i1]:
                    r = R1[i1]
                    h = H1[i1]
                    i1 += 1
                    cnt += 1
                else:
                    i1 += 1
            elif H1[i1] > H2[i2] and R1[i1] > R2[i2]:
                if h < H2[i2] and r < R2[i2]:
                    r = R2[i2]
                    h = H2[i2]
                    i2 += 1
                    cnt += 1
                else:
                    i2 += 1

    print cnt



if __name__ == "__main__":
    import sys

    while True:
        N = int(raw_input())
        if N == 0:
            sys.exit()
        H1 = [0] * N
        R1 = [0] * N
        for i in xrange(N):
            H1[i], R1[i] = map(int, raw_input().split())
        M = int(raw_input())
        H2 = [0] * M
        R2 = [0] * M
        for i in xrange(M):
            H2[i], R2[i] = map(int, raw_input().split())

        solve(N, M, H1, R1, H2, R2)

Submission status: Time Limit Exceeded

Solution code:
def storage(Ls,Size,n):
	flag=0
	mx=0
	for i in range(len(Ls)):
		ls=Ls[:]
		if ls[i][0]<Size[0] and ls[i][1]<Size[1]:
			size=ls.pop(i)
			mx=max(mx,storage(ls,size,n+1))
			flag=1
	return mx if flag==1 else n

while 1:
	n=input()
	if n==0:break
	taro=[map(int,raw_input().split()) for i in range(n)]
	m=input()
	jiro=[map(int,raw_input().split()) for i in range(m)]
	merge=sorted(taro+jiro)[::-1]
	print storage(merge,[1000,1000],0)

Submission status: Time Limit Exceeded

Solution code:
def storage(Ls,Size,n):
	flag=0
	mx=0
	for i in range(len(Ls)):
		ls=Ls[:]
		if ls[i][0]<Size[0] and ls[i][1]<Size[1]:
			size=ls.pop(i)
			mx=max(mx,storage(ls[i:],size,n+1))
			flag=1
	return mx if flag==1 else n

while 1:
	n=input()
	if n==0:break
	taro=[map(int,raw_input().split()) for i in range(n)]
	m=input()
	jiro=[map(int,raw_input().split()) for i in range(m)]
	merge=sorted(taro+jiro)[::-1]
	print storage(merge,[1000,1000],0)

Submission status: Accepted

Solution code:
def In(n): return [map(int, raw_input().split()) for _ in [0]*n]
  
while 1:
  n = int(raw_input())
  if n==0: break
  M1 = In(n)
  m = int(raw_input())
  M2 = In(m)
  j=0
  f1 = [-1 for _ in [0]*n]
  f2 = [-1 for _ in [0]*m]
  for i in range(n):
    h1, r1 = M1[i]
    for j in range(m):
      h2, r2 = M2[j]
      if h1 < h2 and r1 < r2: f2[j] = i
      if h1 > h2 and r1 > r2: f1[i] = j
  c1 = [-1 for _ in [0]*(n+1)]
  c2 = [-1 for _ in [0]*(m+1)]
  p1 = p2 = 0
  while p1<n or p2<m:
    if p1<n:
      if f1[p1]<0:
        if p1==0: c1[0]=1
        else: c1[p1] = c1[p1-1] + 1
        p1+=1
      elif c2[f1[p1]]>=0:
        c1[p1] = max(c1[p1-1], c2[f1[p1]]) + 1
        p1+=1
    if p2<m:
      if f2[p2]<0:
        if p2==0: c2[0]=1
        else: c2[p2] = c2[p2-1]+1
        p2+=1
      elif c1[f2[p2]]>=0:
        c2[p2] = max(c2[p2-1], c1[f2[p2]]) + 1
        p2+=1
  print max(c1+c2)

Submission status: Accepted

Solution code:
# AOJ 0157: Russian Dolls
# Python3 2018.6.19 bal4u
#   単調増加シーケンスの最長値問題（LIS）

def LIS(hr):
	n = len(hr)
	lis = [0]*n
	lis[n-1] = 1;
	for i in range(n-2, -1, -1):
		m = 0;
		for j in range(i+1, n):
			if hr[i][0] < hr[j][0] and hr[i][1] < hr[j][1] and lis[j] > m: m = lis[j]
		lis[i] = m+1
	return lis[0]

while True:
	n = int(input())
	if n == 0: break
	hr = []
	for i in range(n):
		hr.append(list(map(int, input().split())))
	for i in range(int(input())):
		hr.append(list(map(int, input().split())))
	hr = list(sorted(hr))
	print(LIS(hr))

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:
    break
  hr_lst = []
  for _ in range(n):
    h, r = map(int, input().split())
    hr_lst.append((h, r))
  
  m = int(input())
  for _ in range(m):
    h, r = map(int, input().split())
    hr_lst.append((h, r))
  
  hr_lst.sort(reverse=True)

  r_lst = [[] for _ in range(1001)]
  for h, r in hr_lst:
    r_lst[h].append(r)
  r_lst = [lst for lst in r_lst if lst != []]
  
  """
  dp[y] ... 最大yまでの最大入れ子数
  dp[y] = max(dp[y], dp[v - 1] + 1)
  """
  dp = [0] * 1001
  for x in range(len(r_lst)):
    vlst = r_lst[x]
    max_v = 1000
    for v in vlst:
      for y in range(max_v, v - 1, -1):
        dp[y] = max(dp[y], dp[v - 1] + 1)
  print(dp[1000])

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:
    break
  hr_lst = []
  for _ in range(n):
    h, r = map(int, input().split())
    hr_lst.append((h, r))
  
  m = int(input())
  for _ in range(m):
    h, r = map(int, input().split())
    hr_lst.append((h, r))
  
  hr_lst.sort(reverse=True)

  r_lst = [[] for _ in range(1001)]
  for h, r in hr_lst:
    r_lst[h].append(r)
  r_lst = [lst for lst in r_lst if lst != []]
  
  """
  dp[y] ... 最大yまでの最大入れ子数
  dp[y] = max(dp[y], dp[v - 1] + 1)
  """
  dp = [0] * 1001
  for x in range(len(r_lst)):
    vlst = r_lst[x]
    max_v = 1000
    for v in vlst:
      dpv1 = dp[v - 1] + 1
      for y in range(max_v, v - 1, -1):
        if dp[y] < dpv1:
          dp[y] = dpv1
  print(dp[1000])

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:
    break
  hr_lst = []
  for _ in range(n):
    h, r = map(int, input().split())
    hr_lst.append((h, r))
  
  m = int(input())
  for _ in range(m):
    h, r = map(int, input().split())
    hr_lst.append((h, r))
  
  hr_lst.sort(reverse=True)

  r_lst = [[] for _ in range(1001)]
  for h, r in hr_lst:
    r_lst[h].append(r)
  r_lst = [lst for lst in r_lst if lst != []]
  
  """
  dp[y] ... 最大yまでの最大入れ子数
  dp[y] = max(dp[y], dp[v - 1] + 1)
  """
  dp = [0] * 1001
  for x in range(len(r_lst)):
    vlst = r_lst[x]
    max_v = 1000
    for v in vlst:
      dpv1 = dp[v - 1] + 1
      for y in range(max_v, v - 1, -1):
        if dp[y] < dpv1:
          dp[y] = dpv1
      max_v = v
  print(dp[1000])

Submission status: Accepted

Solution code:
while True:
    try:
        L = [map(int,raw_input().split()) for _ in xrange(input())]
        L += [map(int,raw_input().split()) for _ in xrange(input())]
    except EOFError:
        break
    L.sort(key = lambda (h,r):r*r*h)
    DP = [1]*len(L)
    for i,(h,r) in enumerate(L):
        for j,(H,R) in enumerate(L):
            if j > i and (H>h and R>r):
                DP[j] = max(DP[j],DP[i]+1)
    print max(DP)

Submission status: Accepted

Solution code:
while 1:
    n = int(input())
    if n == 0:
        break
    objects = []
    for i in range(n):
        h,r = (int(x) for x in input().split())
        objects.append((h,r))
    n = int(input())
    for i in range(n):
        h,r = (int(x) for x in input().split())
        objects.append((h,r))

    objects = sorted(objects,key=lambda w:(w[0],-1*w[1]))
    r = [i[1] for i in objects]
    t = [1] * len(r)
    
    for i in range(len(r)):
        for j in range(i):
            if r[j] < r[i]:
                t[i] = max(t[i],t[j] + 1)
    print(max(t))

Submission status: Accepted

Solution code:
while 1:
    N = int(input())
    if not N:
        break
    S = []
    for i in range(N):
        h, r = map(int, input().split())
        S.append((h, r))
    M = int(input())
    for i in range(M):
        h, r = map(int, input().split())
        S.append((h, r))

    S.sort()
    memo = [-1]*(N+M)
    def dfs(i):
        if memo[i] != -1:
            return memo[i]
        hi, ri = S[i]
        r = 0
        for j in range(i+1, N+M):
            hj, rj = S[j]
            if hi < hj and ri < rj:
                r = max(r, dfs(j))
        memo[i] = r+1
        return r+1
    print(dfs(0))

Submission status: Accepted

Solution code:
while True:
    n=int(input())
    if n==0:
        break
    dolls=[]
    for i in range(n):
        h,r=[int(j) for j in input().split(" ")]
        dolls.append((h,r))
    m=int(input())
    for j in range(m):
        h,r=[int(j) for j in input().split(" ")]
        dolls.append((h,r))

    dolls=sorted(dolls,key=lambda w:(w[0],-1*w[1]))
    r=[i[1] for i in dolls]

    table=[1 for i in range(len(r))]
    for i in range(len(r)):
        for j in range(i):
            if r[j]<r[i]:
                table[i]=max(table[i],table[j]+1)

    print(max(table))