SP1839 BOOKCASE - The Bookcase

汤姆的旧书架因为摆放了太多书而不堪重负，最终倒塌了。他决定建一个新书架，这次要足够大能放下所有的书。然而，汤姆希望新书架紧凑一些，可以直接放在桌子的后面，方便工作时随手取书。但这会给书架的尺寸带来一些限制：最好是尽可能小。此外，汤姆希望书架有三层，出于美观的考虑。 为了计算出书架的最小尺寸，他将问题转化为以下模型：首先记录每本书的高度 $h_i$ 和厚度 $t_i$，并寻找一个方法，将这些书分成三个非空的集合 $S_1, S_2, S_3$，使得 $$ \max(\sum_{i \in S_1} t_i, \sum_{i \in S_2} t_i, \sum_{i \in S_3} t_i) \times (\max_{i \in S_1} h_i + \max_{i \in S_2} h_i + \max_{i \in S_3} h_i) $$ 达到最小化。这里的宽度是这三个集合中总厚度最大的，而高度是所有集合中最大高度之和。这个公式给出了简化的书架正面面积，不考虑隔板造成的额外高度和侧边增加的宽度。 汤姆意识到这个问题需要用计算机程序来解决。

第一行为一个正整数，表示测试用例的数量（最多 20 个）。对于每个测试用例，第一行为一个正整数 $N$（3 ≤ $N$ ≤ 70），表示书的数量。接下来的 $N$ 行中，每行有两个正整数 $h_i, t_i$，分别表示第 $i$ 本书的高度和厚度，单位为毫米（150 ≤ $h_i$ ≤ 300, 5 ≤ $t_i$ ≤ 30）。

对于每个测试用例，输出一行，给出三层书架的最小正面面积（高度乘以宽度），单位为平方毫米。 **本翻译由 AI 自动生成**