Bookcase Construction

Time limit5sMemory limit128 MB

Summary

Partition n books into three non-empty groups to minimize the sum of per-shelf maximum heights times the maximum total thickness of any shelf.

Level: Medium7 of 10
Topics: Dynamic programming, Sorting, Brute force
Solved: No attempts yet

Problem

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.

Input

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.

Output

Print the minimum possible area of the bookcase.

Constraints

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

Examples2

Example 1
Input
```
4
220 29
195 20
200 9
180 30
```
Expected output
```
18000
```

Example 2

Input

Expected output