Bookcase Construction

Sangjin wants to build a bookcase for n books. For appearance, the bookcase must be divided into exactly three shelves. Each book must be placed on exactly one shelf, and every shelf must contain at least one book.

Let h_i be the height of the i-th book and t_i be its thickness. If S_1, S_2, and S_3 are the sets of books placed on the three shelves, the area of the bookcase is defined as follows.

[ \left(\sum_{j=1}^{3} \max_{i \in S_j} h_i\right) \times \left(\max_{1 \le j \le 3} \sum_{i \in S_j} t_i\right) ]

The height of each shelf is the maximum height among the books on that shelf, and the total width of the bookcase is the largest sum of book thicknesses among the three shelves. Find the minimum possible area after placing all books on the three shelves.

The first line contains the number of books n. Each of the next n lines contains two integers h_i and t_i, the height and thickness of one book.

Print the minimum possible area of the bookcase.

• 3 ≤ n ≤ 70
• 150 ≤ h_i ≤ 300
• 5 ≤ t_i ≤ 30