50137. Stack Rectangles

I'm a slow walker, but I never walk backwards.

Task Description

There are $n$ rectangles with given width and length, and they are indexed from $0$ to $n-1$. The task is to choose and stack the maximum number of them.

One rectangle A can only stack on the top of another rectangle B if A has a larger index than B, and A can fit on top of B. That is, none part of A is not covered by B. Note that we can rotate a rectangle, but only by 90 degrees. Note that by this definition one rectangle fits on top of another rectangle of the same width and length. In the following figure, the red rectangle fits on top of the blue rectangle after we rotate it by 90 degrees.

samplesample

We may find many ways to stack the maximum number of rectangles, so we will only report the one that has has the maximum sum of indices of rectangles. For example, if we find two ways to stack the maximum number $3$ of rectangles, i.e., 0 1 2 and 0 1 3, we report 0 1 3 since is has the maximum sum of indices.

Input Format

The input only has one test case. The first line is the number of rectangles $n$. The following $n$ lines are the width $w$ and length $l$ for each rectangles.

  • $0 \lt n \leq 200$
  • $0 \lt w, l \leq 1000$

Output Format

The output has two integers, the maximum number of rectangles we can stacked and the maximum sum of indices among all possible ways to stack the maximum number of rectangles.

Subtasks

  • 10 points: There are only two rectangles.
  • 40 points: All rectangles are squares, that is, you never rotate them.
  • 50 points: There are no restrictions on rectangles except the ones from the input format.

Sample Input 1

2
1 2
2 1

Sample Output 1

2 1

Sample Input 2

4
4 4
3 3
1 1
2 2

Sample Output 2

3 4

Sample Input 3

5
25 377
105 157
919 657
317 174
121 362

Sample Output 3

2 6

Discussion