Tom có 𝑛 quyển sách, quyển thứ 𝑖 có chiều cao ℎ_𝑖 , chiều rộng 𝑡_𝑖. 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ả 𝑛 quyển sách.

Giả sử 𝑛 quyển sách được phân thành 3 tập không rỗng 𝑆₁, 𝑆₂, 𝑆₃ (các quyển sách thuộc tập 𝑆_𝑖 được xếp vào tầng 𝑖) 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 𝑛 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.

Dữ liệu:

- Dòng đầu là số nguyên dương 𝑛;
- 𝑛 dòng tiếp theo mỗi dòng 2 số ℎ𝑖 ,𝑡𝑖 (150 ≤ ℎ𝑖 ≤ 300, 5 ≤ 𝑡𝑖 ≤ 30)

Kết quả:

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