#P2160. [SHOI2007] 书柜的尺寸

    ID: 1178 远端评测题 5000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp排序数论数学各省省选2007上海

[SHOI2007] 书柜的尺寸

题目描述

Tom 不喜欢那种一字长龙式的大书架,他只想要一个小书柜来存放他的系列工具书。Tom 打算把书柜放在桌子的后面,这样需要查书的时候就可以不用起身离开了。

显然,这种书柜不能太大,Tom 希望它的体积越小越好。另外,出于他的审美要求,他只想要一个三层的书柜。为了物尽其用,Tom 规定每层必须至少放一本书。现在的问题是,Tom 怎么分配他的工具书,才能让木匠造出最小的书柜来呢?

Tom很快意识到这是一个数学问题。每本书都有自己的高度 hih_i 和厚度 tit_i。我们需要求的是一个分配方案,也就是要求把所有的书分配在 S1S_1S2S_2S3S_3 三个非空集合里面的一个,不重复也不遗漏,那么,很明显,书柜正面表面积(SS)的计算公式就是:

$$S=\left(\sum_{j=1}^3 \max_{i \in S_j} h_i\right) \times \left(\max_{j=1}^3 \sum_{i \in S_j} t_i\right) $$

由于书柜的深度是固定的(显然,它应该等于那本最宽的书的长度),所以要求书柜的体积最小就是要求 SS 最小。Tom 离答案只有一步之遥了。不过很遗憾,Tom 并不擅长于编程,于是他邀请你来帮助他解决这个问题。

输入格式

第一行一个整数 nn,代表书本的个数。

接下来 nn 行每行有两个整数 hih_itit_i,代表每本书的高度和厚度。

输出格式

只有一行,即输出最小的 SS

4
220 29
195 20
200 9
180 30
18000

提示

对于全部数据,3n703 \leq n \leq 70150hi300150 \leq h_i \leq 3005ti305 \leq t_i \leq 30