书架 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) 



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

18000
29796