Ảnh Tập Thể 2

Có $n$ người bạn cùng chụp một tấm ảnh tập thể. Trên ảnh, mỗi người chiếm một hình chữ nhật:

• Nếu người thứ $i$ đứng, họ chiếm hình chữ nhật rộng $w_i$ và cao $h_i$.
• Nếu người thứ $i$ nằm, họ chiếm hình chữ nhật rộng $h_i$ và cao $w_i$ (tức là xoay hình chữ nhật đi $90$ độ).

Tất cả mọi người được xếp cạnh nhau theo một hàng ngang. Tấm ảnh khi đó có kích thước $W\times H$, trong đó:

• $W$ là tổng chiều rộng của tất cả các hình chữ nhật.
• $H$ là chiều cao lớn nhất trong tất cả các hình chữ nhật.

Để tấm ảnh trông tự nhiên, không quá $\lfloor n/2\rfloor$ người được phép nằm. Hãy tìm diện tích $W\times H$ nhỏ nhất có thể của tấm ảnh.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$, số lượng người.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $w_i$ và $h_i$, kích thước hình chữ nhật của người thứ $i$.

Dữ liệu ra

• In ra một số nguyên duy nhất là diện tích nhỏ nhất có thể của tấm ảnh.

Ràng buộc

• $1\le n\le 1000$
• $1\le w_i,h_i\le 1000$

Ví dụ