AT_scpc2026_div1_h.SCSC Card Game

SCSC has $N$ members. Each member has one spade card and one club card. Member $i$'s spade card has integer $S_i$ written on it, and their club card has integer $C_i$ written on it.

The members of SCSC are standing in a line in the order from member $1$ to member $N$ to play the SCSC card game. Terra, the host of the game, must choose two adjacent members and make them play one of the following two duels.

• The two members each reveal the spade card with the smallest integer among their spade cards. The member who reveals the card with the larger integer wins. The losing member gives all of their club cards to the winning member and leaves.

• The two members each reveal the club card with the smallest integer among their club cards. The member who reveals the card with the larger integer wins. The losing member gives all of their spade cards to the winning member and leaves.

Any cards that the leaving member does not give to the winning member are no longer used in the game. If there were members on both sides of the leaving member, those two members become adjacent to each other.

After $N-1$ duels, exactly one member remains.

The last remaining member gives Terra one card with the smallest integer among their spade cards and one card with the smallest integer among their club cards, then leaves.

Let $S_{\mathrm{sum}}$ be the sum of the integers written on all spade cards initially held by all members, and let $C_{\mathrm{sum}}$ be the sum of the integers written on all club cards initially held by all members. Let $S_f$ be the integer written on the spade card Terra receives at the end, and let $C_f$ be the integer written on the club card Terra receives at the end. Then Terra's final score is $(S_{\mathrm{sum}} - S_f)(C_{\mathrm{sum}} - C_f)$.

Terra wants the final score to be as small as possible. Find the minimum possible score Terra can obtain.

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 能获得的最小可能得分。

The input is given from Standard Input in the following format:

$N$
$S_1$ $C_1$
$S_2$ $C_2$
$\vdots$
$S_N$ $C_N$

输入从标准输入中按以下格式给出：

$N$
$S_1$ $C_1$
$S_2$ $C_2$
$\vdots$
$S_N$ $C_N$

Output the minimum possible score Terra can obtain.

输出Terra能够获得的最小可能得分。

表示言語

/ /

Constraints

• $1 \leq N \leq 5\,000$
• $1 \leq S_i, C_i \leq 50\,000$
• For all $1 \leq i < j \leq N$, $S_i \neq S_j$ and $C_i \neq C_j$.
• All given numbers are integers.

表示语言

/ /

限制条件

• $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$。
• 所有给定的数均为整数。