AT_scpc2026_div1_h SCSC Card Game

#### 表示言語 / / SCSC には $ N $ 人の部員がいる．各部員は **スペードカード** と **クラブカード** を $ 1 $ 枚ずつ持っている．部員 $ i $ が持つスペードカードには整数 $ S_i $ が，クラブカードには整数 $ C_i $ が書かれている． SCSC の部員たちは，SCSC カードゲームをするために $ 1 $ 番から $ N $ 番まで順番に一列に並んでいる．ゲームの進行役であるテラは，隣り合う $ 2 $ 人の部員を選び，次の $ 2 $ 種類の対戦のうち一方をさせなければならない． - $ 2 $ 人の部員がそれぞれ，自分が持つスペードカードのうち書かれている整数が最も小さいカードを公開する．より大きい整数が書かれたカードを公開した部員が勝利する．敗北した部員は自分が持つクラブカードをすべて勝利した部員に渡して退場する． - $ 2 $ 人の部員がそれぞれ，自分が持つクラブカードのうち書かれている整数が最も小さいカードを公開する．より大きい整数が書かれたカードを公開した部員が勝利する．敗北した部員は自分が持つスペードカードをすべて勝利した部員に渡して退場する． 退場した部員が勝利した部員に渡さなかったカードは，以後ゲームでは使用されない．退場した部員の両隣に部員がともに存在した場合，その $ 2 $ 人の部員は新たに隣り合うことになる． $ N-1 $ 回の対戦を行うと，最後にはただ $ 1 $ 人の部員だけが残る． 最後に残った部員は，自分が持つスペードカードのうち書かれている整数が最も小さいカード $ 1 $ 枚と，クラブカードのうち書かれている整数が最も小さいカード $ 1 $ 枚をテラに渡して退場する． 最初にすべての部員が持つスペードカードに書かれた整数の合計を $ S_{\mathrm{sum}} $ ，クラブカードに書かれた整数の合計を $ C_{\mathrm{sum}} $ とする．最後にテラが受け取ったスペードカードに書かれた整数を $ S_f $ ，クラブカードに書かれた整数を $ C_f $ とすると，テラの最終得点は $ (S_{\mathrm{sum}} - S_f)(C_{\mathrm{sum}} - C_f) $ となる． テラは最後に得られる得点をできるだけ小さくしたい．テラが得られる得点の最小値を求めよ．

入力は以下の形式で標準入力から与えられる． > $ N $ $ S_1 $ $ C_1 $ $ S_2 $ $ C_2 $ $ \vdots $ $ S_N $ $ C_N $

テラが得られる得点の最小値を出力せよ．

### Constraints - $ 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 $ である． - 入力される数値はすべて整数である．