表示言語
/ /分数: 100 点
问题陈述
SCSC 有 N 成员。每个成员都有一个 黑桃牌 和一个 俱乐部卡。会员 i的黑桃牌有整数 上面写着 S_i ,他们的俱乐部卡上有整数 C_i 。
SCSC成员按照成员顺序排队 1 致会员 N 玩 SCSC 纸牌游戏。游戏的主办方 Terra 必须选择两名相邻的成员,让他们进行以下两场决斗之一。
-
两名成员各自亮出黑桃牌中整数最小的黑桃牌。翻开具有较大整数的卡片的成员获胜。失败的会员将所有俱乐部卡交给获胜的会员并离开。
-
两名成员各自亮出其俱乐部卡中整数最小的俱乐部卡。翻开具有较大整数的卡片的成员获胜。失败的成员将所有黑桃牌交给获胜的成员并离开。
离开会员未给予获胜会员的任何卡牌将不再在游戏中使用。如果离开成员的两侧都有成员,则这两个成员变得彼此相邻。
之后 N-1 决斗,只剩下一名成员。
最后剩下的成员给泰拉一张黑桃牌中最小整数的牌和一张俱乐部牌中最小整数的牌,然后离开。
让 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 可以获得的最低可能分数。
约束
- 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
输出
输出 Terra 可以获得的最小可能分数。
示例输入 1
2 3 4 4 5
示例输出 1
15
表示言語
/ /分数: 100 点
문제
SCSC N명의 부원이 있다. 각 부원은 스페이드 카드와 클로버 카드를 한 장씩 가지고 있다. i번 부원이 가진 스페이드 카드에는 정수 S_i, 클로버 카드에는 정수 C_i가 적혀 있다.
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