Description

俄羅斯娃娃是一種特別的木製玩具,由一個大娃娃包住一個小娃娃。
可以向俄羅斯娃娃許願,每個娃娃有法力值,法力值越高,代表願望越有可能成真。

現在有 $n$ 個大娃娃排成一圈,順時針數來的法力值為 $a_0\sim a_{n-1}$;與 $n$ 個小娃娃排成一圈,順時針數來的法力值為 $b_0\sim b_{n-1}$。

因為某種特別的迷信(?),小娃娃的法力值是非嚴格遞增的,也就是 $b_0\leq b_1\leq\dots\leq b_{n-1}$。

你可以將小娃娃順時針轉 $k$ 格($0\leq k<n$),並將對應到的大娃娃包住小娃娃,也就是讓編號 $(i+k)\text{ mod }n$ 的大娃娃包住編號 $i$ 的小娃娃。我們稱此俄羅斯娃娃的法力值為大娃娃與小娃娃的法力值總和,也就是 $a_{(i+k)\text{ mod }n}+b_i$。

願望成真的程度與 $n$ 個俄羅斯娃娃法力值的最小值 $S$ 有關,為了使願望成真,你想使 $S$ 越大越好,請你輸出在適當的轉小娃娃後,$S$ 最大可以是多少。

Input Format

第一行有一個正整數 $n$,代表大娃娃與小娃娃的數量。
第二行有 $n$ 個正整數 $a_0\sim a_{n-1}$,代表大娃娃的法力值。
第三行有 $n$ 個正整數 $b_0\sim b_{n-1}$,代表小娃娃的法力值。

對於所有測試資料:

  • $3\leq n\leq 10^ 5$
  • $1\leq a_i,b_i\leq 10^ {18}$($0\leq i<n$)
  • $b_i\leq b_{i+1}$($0\leq i\leq n-2$)

Output Format

輸出一個整數 $S$,代表在適當的轉小娃娃後,俄羅斯娃娃法力值的最小值 $S$ 最大可以是多少。

Sample Input 1

3
20 10 30
1 3 15

Sample Output 1

23

Sample Input 2

10
395 846 120 567 719 523 162 99 48 311
74 85 241 322 341 415 421 595 705 720

Sample Output 2

440

Hints

$x\text{ mod }y$ 代表 $x$ 對 $y$ 取模,也就是 $x$ 除以 $y$ 的餘數

在範例測資一中:
將小娃娃順時針轉 $k=2$ 格會使 $S$ 最大,此時 $S=\min(20+3,10+15,30+1)=23$

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~13, 38~39 $n\leq 10^ 3$ 22
3 5~10, 17~22, 29~34 $a_i\leq a_{i+1}$($0\leq i\leq n-2$) 20
4 0~43 無其他限制 58

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 65536 1 2 4
1 1000 131072 65536 1 2 4
2 1000 131072 65536 2 4
3 1000 131072 65536 2 4
4 1000 131072 65536 2 4
5 1000 131072 65536 2 3 4
6 1000 131072 65536 2 3 4
7 1000 131072 65536 2 3 4
8 1000 131072 65536 2 3 4
9 1000 131072 65536 2 3 4
10 1000 131072 65536 2 3 4
11 1000 131072 65536 2 4
12 1000 131072 65536 2 4
13 1000 131072 65536 2 4
14 1000 131072 65536 4
15 1000 131072 65536 4
16 1000 131072 65536 4
17 1000 131072 65536 3 4
18 1000 131072 65536 3 4
19 1000 131072 65536 3 4
20 1000 131072 65536 3 4
21 1000 131072 65536 3 4
22 1000 131072 65536 3 4
23 1000 131072 65536 4
24 1000 131072 65536 4
25 1000 131072 65536 4
26 1000 131072 65536 4
27 1000 131072 65536 4
28 1000 131072 65536 4
29 1000 131072 65536 3 4
30 1000 131072 65536 3 4
31 1000 131072 65536 3 4
32 1000 131072 65536 3 4
33 1000 131072 65536 3 4
34 1000 131072 65536 3 4
35 1000 131072 65536 4
36 1000 131072 65536 4
37 1000 131072 65536 4
38 1000 131072 65536 2 4
39 1000 131072 65536 2 4
40 1000 131072 65536 4
41 1000 131072 65536 4
42 1000 131072 65536 4
43 1000 131072 65536 4