CF589B Layer Cake

Dasha 决定烤一个又大又美味的多层蛋糕。为此，她去购物买了 $n$ 层矩形蛋糕胚。第 $i$ 层蛋糕胚的长和宽分别为 $a_{i}$ 和 $b_{i}$，每一层的高都等于 $1$。 Dasha 从一本烹饪书上得知，蛋糕必须是由相同尺寸的蛋糕层堆叠而成的长方体。 Dasha 想用买来的蛋糕胚做出体积尽可能大的蛋糕（可以只使用其中一部分蛋糕胚）。这意味着她希望蛋糕的体积最大。为此，她可以从买来的蛋糕胚中裁剪出矩形块。她总是以与原蛋糕胚边平行的方式裁剪。Dasha 并不擅长几何，因此在裁剪出需要的部分后，其余部分都会被丢弃。她还可以将任一蛋糕胚在水平面上旋转（即交换其长和宽）。 Dasha 希望蛋糕可以由尺寸完全相同的蛋糕层堆叠而成，每层只能使用一个蛋糕胚（无论是原尺寸还是裁剪后）。请你帮 Dasha 计算她最多能烤出多大体积的蛋糕，并给出所用蛋糕层的长宽。

第一行包含一个整数 $n$（$1 \le n \le 4000$），表示 Dasha 可以使用的蛋糕胚数量。 接下来 $n$ 行，每行包含两个整数 $a_{i}$ 和 $b_{i}$（$1 \le a_{i}, b_{i} \le 10^{6}$），表示第 $i$ 个蛋糕胚的长和宽。

输出两行。 第一行输出能烤出的最大体积。 第二行输出蛋糕层的长和宽。如果有多个最大体积的方案，输出任意一个均可。

在第一个样例中，Dasha 没有使用第二块蛋糕胚。她从第一块蛋糕胚中裁剪出 $4\times 6$ 的矩形，并且直接使用其它蛋糕胚。 在第二个样例中，Dasha 需要对两块蛋糕胚都进行少量裁剪。 由 ChatGPT 5 翻译