타일 블록 쌓기

마이클은 생일 선물로 조부모에게서 게임 세트를 받았다. 상자 안에는 타일 블록 $n$개가 들어 있고, 블록의 모양은 다음과 같다.

그림 1: 파라미터가 $(3, 2)$인 타일 블록.

블록마다 파라미터 $(\ell, m)$이 정해져 있다. 윗면에는 왼쪽에 돌기가 $\ell$개, 가운데에 돌기가 $m$개 튀어나와 있고, 아랫면에는 같은 자리에 왼쪽 $\ell$개, 가운데 $m$개의 홈이 파여 있다.

$(\ell, m)$ 블록을 같은 $(\ell, m)$ 블록 위에 올릴 수 있다는 것은 쉽게 알 수 있다. 쌓는 방법은 이것만이 아니다. $(\ell, m)$ 블록을 $(\ell', m')$ 블록 위에 올릴 수 있는 조건은 $\ell \ge \ell'$이고 $m \ge m'$인 것이며, 이 조건을 만족할 때만 올릴 수 있다.

블록 $n$개가 담긴 상자 $B = \{b_1, b_2, \dots, b_n\}$가 주어진다. 블록 $b_i$의 파라미터는 $(\ell_i, m_i)$이다. 이 상자의 블록으로 탑을 쌓을 때, 가장 높은 탑에 들어가는 블록의 개수를 구하라.

입력에는 게임 상자 여러 개가 이어서 주어진다. 각 상자는 정수 $n$으로 시작하고, $n$은 그 상자에 든 블록의 개수다. 이어지는 $n$개 줄에는 각각 정수 두 개가 주어지며, $i$번째 블록의 왼쪽 파라미터 $\ell_i$와 가운데 파라미터 $m_i$를 뜻한다.

$n$은 최대 $10\,000$이고, $\ell_i$와 $m_i$는 $1$ 이상 $100$ 이하다. $n = 0$은 입력의 끝을 뜻한다.

상자마다 그 상자의 블록으로 쌓을 수 있는 가장 높은 탑의 블록 개수를 한 줄에 하나씩 출력한다. 모든 상자를 처리한 뒤에는 마지막 줄에 별표 * 하나만 출력한다.