Building Blocks
면접 대비시간 제한1초메모리 제한1024 MB
너비와 길이가 주어진 최대 100개의 블록을 아래 블록보다 두 변이 크지 않도록 쌓을 때 만들 수 있는 가장 높은 탑의 높이를 구한다.
문제
The cows want to build a tower out of the blocks they found. They want you to tell them how high the tower will be, given the sizes of the blocks. Each block has a width and length in addition to being one unit in height. The blocks must be stacked with all their edges parallel to a set of axes, and the blocks can be rotated 90 degrees, if you wish. In order to build a stable tower, each higher block must be no larger than the block on which it sits -- both the width and the length of each higher block must be no larger than the width and length of the block upon which it sits.
Your job is to determine the height of the tallest possible stable tower that can be built with a given collection of blocks.
입력
- Line 1: one integer: B, 1 ≤ B ≤ 100, the number of blocks
- Line 2..B+1: B lines, each with two integers denoting the width and length of a square block. Each of these dimensions is at least one unit and at most 100 units.
출력
A single line with an integer telling how high the tallest possible stable tower can be.