CF529B Group Photo 2 (online mirror version)

许多年过去了，$n$ 位朋友再次在聚会上相聚。自上次见面以来，科技得到了飞跃发展，带有定时器的相机出现了，这样就不必再有一位朋友站着拿相机，从而无法出现在合影中了。 简而言之，拍照的过程可以描述如下。每位朋友在照片上占据一个像素矩形：第 $i$ 位朋友站立时占据一个宽为 $w_{i}$，高为 $h_{i}$ 的矩形。但是，每个人也可以为了照片而躺下，这样他就会占据一个宽为 $h_{i}$，高为 $w_{i}$ 的矩形。 最终合影的尺寸为 $W \times H$，其中 $W$ 是所有人的矩形宽度之和，$H$ 是所有人的最大高度。朋友们希望确定在不超过 $n/2$ 的人躺下的情况下，所能获得的合照最小面积。 请你帮助他们实现这个目标。

第一行包含一个整数 $n$（$1 \leq n \leq 1000$），表示朋友的人数。 接下来的 $n$ 行，每行包含两个整数 $w_{i}, h_{i}$（$1 \leq w_{i}, h_{i} \leq 1000$），分别表示第 $i$ 位朋友所对应矩形的宽度和高度。

输出一个整数，表示在不超过 $n/2$ 个朋友躺下的前提下，使全体朋友都在照片中的最小可能面积。

由 ChatGPT 5 翻译