书架 The Bookcase

题意翻译

# 题目大意 有 $n$ 本书,每本书有一个高度 $h_i$ 和一个宽度 $w_i$。 现在要构建一个 $3$ 层的书架,你可以选择将 $n$ 本书放在书架的哪一层。设 $3$ 层高度(每层书的最大高度)之和为 $h$,书架总宽度为 $w$,要求 $h×w$ 尽量小。 $3\le n\leq 70,1\leq h_i\leq 300,1\leq w_i\le 30$ 。 # 输入格式 输入包含多组数据(不多于20个); 对于每组数据,第一行有一个正整数$n$,书的数量; 接下来$n$行每行两个正整数$h_i,w_i$,分别代表书的高度、书的宽度。 # 输出格式 对于每组测试数据,输出一行一个正整数,表示书架的最小面积。 感谢@皎月半洒花 提供翻译。

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=242&page=show_problem&problem=3251 [PDF](https://uva.onlinejudge.org/external/120/p12099.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12099/ee0851ffa7e62c4ec96c220f08d00f8736e21958.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12099/3d47314d3f67cde662f48eea6818e41110f7d9eb.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12099/4f7209be687892141cda99217b24f2fd60a4bcc6.png)

输入输出样例

输入样例 #1

2
4
220 29
195 20
200 9
180 30
6
256 20
255 30
254 15
253 20
252 15
251 9

输出样例 #1

18000
29796