AT_scpc2026_div1_h SCSC Card Game

SCSC 有 $N$ 名成员。每位成员都有一张“黑桃牌”和一张“梅花牌”。第 $i$ 位成员的黑桃牌上写有整数 $S_i$，梅花牌上写有整数 $C_i$。 SCSC 的成员们按 $1$ 到 $N$ 的顺序排成一排，进行 SCSC 纸牌游戏。主持人 Terra 必须选择两个相邻成员，使他们进行以下两种对决之一： - 每人亮出当前所有黑桃牌中最小整数那一张。数值较大的一名获胜。失败者将其所有梅花牌交给获胜者，然后离开。 - 每人亮出当前所有梅花牌中最小整数那一张。数值较大的一名获胜。失败者将其所有黑桃牌交给获胜者，然后离开。 离开的成员未交给对手的所有牌将不再参与游戏。如果离开成员两侧都有其他成员，则他们将成为新的一对相邻成员。 经过 $N-1$ 轮对决后，最终只剩下一名成员。 最后剩下的成员将其所有黑桃牌中最小整数那一张，以及所有梅花牌中最小整数那一张交给 Terra，然后离开。 设 $S_{\mathrm{sum}}$ 为游戏初始时所有成员手上黑桃牌上的整数之和，$C_{\mathrm{sum}}$ 为所有成员手上梅花牌上的整数之和。又设 $S_f$ 为 Terra 最终拿到的那张黑桃牌上的整数，$C_f$ 为 Terra 最终拿到的那张梅花牌上的整数。那么 Terra 的最终得分为 $(S_{\mathrm{sum}} - S_f)(C_{\mathrm{sum}} - C_f)$。 Terra 想要使最终得分尽量小。请你求出 Terra 能得到的最小得分。

输入从标准输入给出，格式如下： > $N$ $S_1$ $C_1$ $S_2$ $C_2$ $\vdots$ $S_N$ $C_N$

输出 Terra 能得到的最小得分。

### 数据范围 - $1 \leq N \leq 5\,000$ - $1 \leq S_i, C_i \leq 50\,000$ - 对于所有 $1 \leq i < j \leq N$，$S_i \neq S_j$ 并且 $C_i \neq C_j$。 - 所有给定的数均为整数。 由 ChatGPT 5 翻译