AT_scpc2026_div2_b 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.

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 $

Output the minimum possible score Terra can obtain.

### 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.