색종이 쌓기

크기가 모두 다른 직사각형 색종이가 여러 장 있다. 색종이를 한 장씩 위에 올려 가능한 한 많이 쌓으려고 한다.

새 색종이는 항상 현재 더미의 맨 위 색종이 위에 놓아야 한다. 이때 다음 두 조건을 모두 만족해야 한다.

• 새 색종이는 맨 위 색종이보다 크지 않아야 한다. 즉, 어떤 부분도 맨 위 색종이 밖으로 나가면 안 된다.
• 새 색종이의 변은 맨 위 색종이의 변과 서로 평행해야 한다. 색종이는 90도 돌려 놓을 수 있다.

아래 네 그림에서 두 조건을 모두 만족하는 배치는 (나)뿐이다.

(가)	(나)	(다)	(라)

색종이는 두 변의 길이로 나타낸다. (3, 5)는 변의 길이가 3과 5인 색종이를 뜻한다. 7장의 색종이가 (1, 2), (8, 7), (20, 10), (20, 20), (15, 12), (12, 14), (11, 12)로 주어지면, 조건을 만족하면서 가장 많이 쌓는 순서 중 하나는 (20, 20), (15, 12), (12, 14), (11, 12), (8, 7), (1, 2)이다.

입력으로 주어진 색종이들로 만들 수 있는 최대 높이, 즉 쌓을 수 있는 색종이의 최대 장수를 구하라.

첫째 줄에 색종이의 장수 N이 주어진다. 다음 N개 줄에는 색종이 한 장의 두 변의 길이가 공백으로 구분되어 주어진다.

색종이는 최대 100장이고, 각 변의 길이는 1000보다 작은 자연수이다.

쌓을 수 있는 색종이의 최대 장수를 출력한다.