User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

60.0% (3/5)

Description

(故事純屬虛構,如有雷同純屬巧合)

今天你想要從成功大學店畢業,需要進行口試,只有通過口試你才能夠從成功大學店畢業!

今天你有 $N$ 個口試委員,他們會依序問你問題,對你造成「疲倦攻擊」,不過好在你可以決定他們問問題的順序,使得你口試受到最少的「疲倦攻擊」!

接下來我們來談談問問題所造成的「疲倦攻擊」,這 $N$ 個口試委員坐在一張超長的長桌面前,當一位口試委員提問時,你受到的「疲倦攻擊」有:

  • 提問者的「言語」造成
  • 提問者左手邊第一位的「眼神」造成(如果有的話)
  • 提問者右手邊第一位的「眼神」造成(如果有的話)
  • 由於口試委員都很忙,所以問完你問題之後就會離開桌子,離開口試現場

以下舉例:
有三個口試委員:
分別能夠造成的「言語疲倦」為「$2$、$5$、$7$」
分別能夠造成的「眼神疲倦」為「$8$、$3$、$0$」

對你來說最好的被提問順序是有左至右,也就是 $1\ 2\ 3$,則:

  • step 1: $2+3$
    $1$ 號造成言語疲倦,右手邊 $2$ 號造成眼神疲倦,左手邊沒人。

  • step 2: $5+0$
    $2$ 號造成言語疲倦,右手邊 $3$ 號造成眼神疲倦,左手邊沒人,因為 $1$ 號已經走了

  • step 3: $7$
    $3$ 號造成言語疲倦,左右手邊都沒人,因為 $1$ 號與 $2$ 號都走了!

  • sum: $17$,你至少會受到 $17$ 點的疲倦攻擊!

如果提問的順序是 $2\ 3\ 1$,則:

  • step 1: $5+8+0$
    $2$ 號造成言語疲倦,右手邊 $3$ 號造成眼神疲倦,左手邊 $1$ 號造成眼神疲倦

  • step 2: $7+8$
    $3$ 號造成言語疲倦,左手邊 $1$ 號造成眼神疲倦,右手邊沒人

  • step 3: $2$
    $1$ 號造成言語疲倦,左右手邊都沒人

  • sum: $30$,你受到 $30$ 點的疲倦攻擊!

Input Format

輸入共有三行,第一行有一個整數 $N$ ($2\leq N\leq 300$) 代表口試委員的人數。
第二行有 $N$ 個整數 ($a_1, a_2 ... a_n$),依序代表各個口試委員能造成的言語疲倦。
第三行有 $N$ 個整數 ($b_1, b_2 ... b_n$),依序代表各個口試委員能造成的眼神疲倦。
($0\leq a_i, b_i \leq 10^9, \forall 1 \leq i \leq N$)

Output Format

輸出只有一個整數,代表你口試受到最少的「疲倦」數。

Sample Input 1

3
2 5 7
8 3 0

Sample Output 1

17

Sample Input 2

10
1 3 5 7 9 2 4 6 8 10
9 4 1 2 1 2 1 4 5 1

Sample Output 2

74

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~16 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1
13 1000 65536 65536 1
14 1000 65536 65536 1
15 1000 65536 65536 1
16 1000 65536 65536 1