Tom có \(n\) quyển sách, quyển thứ \(i\) có chiều cao \(h_i\), chiều rộng \(t_i\). Tom muốn làm một giá sách gồm có \(3\) tầng để có thể chứa hết tất cả \(n\) quyển sách.

Giả sử \(n\) quyển sách được phân thành \(3\) tập không rỗng \(S_1, S_2, S_3\) (các quyển sách thuộc tập \(S_i\) được xếp vào tầng \(i\)) thì cần giá sách chiếm diện tích bằng:

Yêu cầu: Cần tìm cách phân \(n\) quyển sách thành \(3\) tập khác rỗng để giá sách chiếm diện tích nhỏ nhất.

Input

• Dòng đầu là số nguyên dương \(n\).
• \(n\) dòng tiếp theo, mỗi dòng gồm \(2\) số \(h_i, t_i\).
• Ràng buộc:
  • \(150 \le h_i \le 300\)
  • \(5 \le t_i \le 30\)

Output

• Ghi ra diện tích nhỏ nhất của giá sách.

Example

4
220 29
195 20
200 9
180 30

18000

Scoring

• Subtask \(1\): \(n \le 10\); [\(15\) tests]
• Subtask \(2\): \(n \le 20\); [\(15\) tests]
• Subtask \(3\): \(n \le 70\); [\(20\) tests]

Nguồn: 3D'17