Tom does not like long, linear bookshelves; he only wants a small bookcase to store his collection of reference books. Tom plans to place the bookcase behind his desk so that he does not have to get up when he needs to look something up. Obviously, this bookcase cannot be too large, and Tom wants its volume to be as small as possible. Furthermore, due to his aesthetic requirements, he only wants a three-shelf bookcase. To make the best use of space, Tom stipulates that each shelf must contain at least one book. The question now is: how should Tom distribute his reference books so that the carpenter can build the smallest possible bookcase?

Tom soon realized that this is a mathematical problem. Each book has its own height $h_i$ and thickness $t_i$. We need to find an allocation scheme, which means distributing all the books into three non-empty sets $S_1$, $S_2$, and $S_3$ such that every book is assigned to exactly one set. The formula for the front surface area ($S$) of the bookcase is:

$$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 be equal to the length of the widest book), minimizing the volume of the bookcase is equivalent to minimizing $S$. Tom is only one step away from the answer. Unfortunately, Tom is not good at programming, so he invites you to help him solve this problem.

Input

The first line of the file contains a single integer $n$ ($3 \le n \le 70$), representing the number of books. The following $n$ lines each contain two integers $h_i$ and $t_i$, representing the height and thickness of each book, respectively. We guarantee $150 \le h_i \le 300$ and $5 \le t_i \le 30$.

Output

A single line containing the minimum $S$.

Examples

Input 1

4
220 29
195 20
200 9
180 30

Output 1

18000

Input 2

6
256 20
255 30
254 15
253 20
252 15
251 9

Output 2

29796