The contest is ended. New submissions will be treated as correction submissions and will not be counted in the contest.

题目描述

还记得环形石子合并这一题吗？今天要解决的是环形吃石子问题。

在一个环上顺时针排列着 $n$ 堆石子。吃掉第 $i$ 堆石子需要体重大于等于 $a_i$，而吃掉这堆石子之后体重将会增加 $b_i$。

小 F 将会使用这样的方式吃石子：选择一堆石子先吃掉这堆石子，然后依次顺时针吃石子，吃完为止。

小 F 想要吃掉所有石子，请求出小 F 初始体重至少要有多少才能达成目标。

输入格式

第一行一个正整数 $n$。

接下来一行，$n$ 个非负整数 $a_i$，以顺时针方向给出每一堆石子的属性。

接下来一行，$n$ 个非负整数 $b_i$，以顺时针方向给出每一堆石子的属性。

输出格式

输出一行一个整数，表示小 F 初始体重的最小值。

3
1 6 3
2 1 2

3

提示

样例解释

当小 F 的初始体重为 $3$ 时，他可以先吃第 $3$ 堆石子，然后吃第 $1$ 堆石子，最后吃第 $2$ 堆石子。注意，他必须按照顺时针方向吃石子，因此不能先吃第 $1$ 堆石子，然后吃第 $3$ 堆石子，最后吃第 $2$ 堆石子。

数据范围

本题采用捆绑测试。

• Subtask 1（10 分）：$n\le 2\times {10}^3$，答案不超过 $10$。
• Subtask 2（21 分）：$n\le 2\times {10}^3$。
• Subtask 3（19 分）：答案不超过 $10$。
• Subtask 4（22 分）：$b_i=1$。
• Subtask 5（28 分）：无特殊限制。

对于 $100\%$ 的数据， $2\le n\le 5\times {10}^5$，$0\le a_i,b_i\le {10}^9$。