Bookcase Optimization

Tom dislikes huge, long bookshelves. Instead, he wants a compact, three-layer bookcase to store his series of reference books. He plans to place the bookcase behind his desk so that when he needs to consult a book, he does not have to get up.

Since space is at a premium, Tom wants the bookcase to be as small as possible. Furthermore, due to his aesthetic requirements, he insists that the bookcase have exactly three layers, and each shelf must contain at least one book.

Each book has its own height \(h_i\) and thickness \(t_i\). If the books are partitioned into three non-empty sets \(S_1\), \(S_2\), and \(S_3\), the front surface area \(S\) of the bookcase is given by:

$$S=\Bigl(\sum_{j=1}^3 \max_{i\in S_j}h_i\Bigr)\times \Bigl(\max_{j=1}^3 \sum_{i\in S_j}t_i\Bigr) $$

Your task is to determine an assignment of the books to the three shelves (each shelf receiving at least one book) that minimizes \(S\). The smaller the area, the smaller the bookcase!

inputFormat

The first line contains a positive integer \(n\) representing the number of books. Each of the following \(n\) lines contains two positive integers \(h_i\) and \(t_i\), representing the height and thickness of the \(i\)-th book, respectively.

outputFormat

Output a single integer: the minimum possible front surface area \(S\) of the bookcase.

sample

3
10 5
20 3
15 2

225