B - SCSC Card Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

表示言語

/ /

Score : 100 points

Problem Statement

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.

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.

Input

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

Output the minimum possible score Terra can obtain.

Sample Input 1

2
3 4
4 5

Sample Output 1

15

表示言語

/ /

Score : 100 points

문제

SCSC에는 N명의 부원이 있다. 각 부원은 스페이드 카드와 클로버 카드를 한 장씩 가지고 있다. i번 부원이 가진 스페이드 카드에는 정수 S_i, 클로버 카드에는 정수 C_i가 적혀 있다.

SCSC 부원들은 SCSC 카드 놀이를 하기 위해 1번부터 N번까지 순서대로 서 있다. 게임의 진행자인 테라는 인접하게 서 있는 두 부원을 골라 다음 두 가지 대결 중 하나를 시켜야 한다.

  • 두 부원이 각자 자신이 가진 스페이드 카드 중 적힌 수가 가장 작은 카드를 공개한다. 더 큰 수가 적힌 카드를 공개한 부원이 승리한다. 패배한 부원은 자신이 가진 클로버 카드를 모두 승리한 부원에게 넘겨주고 퇴장한다.

  • 두 부원이 각자 자신이 가진 클로버 카드 중 적힌 수가 가장 작은 카드를 공개한다. 더 큰 수가 적힌 카드를 공개한 부원이 승리한다. 패배한 부원은 자신이 가진 스페이드 카드를 모두 승리한 부원에게 넘겨주고 퇴장한다.

퇴장한 부원이 승리한 부원에게 넘겨주지 않은 카드는 더 이상 게임에 사용되지 않는다. 퇴장한 부원의 양옆에 부원이 모두 있었다면 그 두 부원은 새로 인접하게 된다.

N-1번 대결을 하고 나면 마지막에 단 한 명의 부원만 남는다.

마지막에 남은 부원은 자신이 가진 스페이드 카드 중 적힌 수가 가장 작은 카드 한 장과 클로버 카드 중 적힌 수가 가장 작은 카드 한 장을 테라에게 주고 퇴장한다.

처음 모든 부원이 가진 스페이드 카드에 적힌 정수의 합을 S_{\mathrm{sum}}, 클로버 카드에 적힌 정수의 합을 C_{\mathrm{sum}}이라고 하자. 마지막에 테라가 받은 스페이드 카드에 적힌 수를 S_f, 클로버 카드에 적힌 수를 C_f라고 하면, 테라의 최종 점수는 (S_{\mathrm{sum}} - S_f)(C_{\mathrm{sum}} - C_f)가 된다.

테라는 마지막에 얻게 되는 점수를 최소화하고자 한다. 테라가 얻을 수 있는 점수의 최솟값을 구해 보자.

제한

  • 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이다.
  • 입력으로 주어지는 수는 모두 정수이다.

입력

입력은 다음 형식으로 표준 입력으로 주어진다.

N
S_1 C_1
S_2 C_2
\vdots
S_N C_N

출력

테라가 얻을 수 있는 점수의 최솟값을 출력한다.

입력 예 1

2
3 4
4 5

출력 예 1

15

表示言語

/ /

配点 : 100 点

問題文

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) となる．

テラは最後に得られる得点をできるだけ小さくしたい．テラが得られる得点の最小値を求めよ．

制約

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

入力

入力は以下の形式で標準入力から与えられる．

N
S_1 C_1
S_2 C_2
\vdots
S_N C_N

出力

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

入力例 1

2
3 4
4 5

出力例 1

15