P2160 [SHOI2007] Size of the Bookcase

Tom does not like those long, single-row bookshelves. He only wants a small bookcase to store his series of reference books. Tom plans to place the bookcase behind his desk so he does not need to stand up to look things up. Obviously, this bookcase cannot be too large. Tom wants its volume to be as small as possible. Also, for aesthetic reasons, he wants a three-tier bookcase. To make full use of the space, Tom requires that each tier must contain at least one book. Now the question is: how should Tom distribute his reference books so that the carpenter can build the smallest possible bookcase? Tom quickly realized that this is a math problem. Each book has its own height $h_i$ and thickness $t_i$. What we need is an assignment plan, meaning we must assign every book to exactly one of $S_1$, $S_2$, and $S_3$ — the **three non-empty sets** — with no duplication and no omission. Then, it is clear that the front surface area of the bookcase ($S$) is given by: $$S=\left(\sum_{j=1}^3 \max_{i \in S_j} h_i\right) \times \left(\max_{j=1}^3 \sum_{i \in S_j} t_i\right) $$ Since the depth of the bookcase is fixed (obviously, it should equal the length of the widest book), minimizing the volume of the bookcase is equivalent to minimizing $S$. Tom is just one step away from the answer. Unfortunately, Tom is not good at programming, so he invites you to help him solve this problem.

The first line contains an integer $n$, the number of books. Each of the next $n$ lines contains two integers $h_i$ and $t_i$, representing the height and thickness of each book.

Output a single line: the minimal $S$.

Constraints: for all testdata, $3 \leq n \leq 70$, $150 \leq h_i \leq 300$, $5 \leq t_i \leq 30$. Translated by ChatGPT 5