分苹果

题目描述

有 $n$ 个孩子，从 $1$ 到 $n$ 编号，编号为 $i$ 的孩子握着 $a_i$ 个苹果。又有 $n$ 个筐，从 $1$ 到 $n$ 编号，编号为 $i$ 的筐可以最多装下 $b_i$ 个苹果。

对于 $1$ 到 $n$ 中任何的正整数 $i$，编号为 $i$ 的孩子可以把手上的苹果按任意数量分配到编号为 $i$ 和编号为 $(i \bmod n + 1)$ 的筐里，若不把苹果放在筐里，小朋友也可以把苹果留在手上。

请设计一个方案，使得装到筐里的苹果总数达到最大。

输入格式

第一行：单个整数 $n$； 第二行：$n$ 个整数 $a_1, a_2, \ldots, a_n$； 第三行：$n$ 个整数 $b_1, b_2, \ldots, b_n$。

输出格式

单个整数：表示能装入筐的最多苹果数量。

样例输入 #1

5
4 1 0 2 2
2 0 0 1 6

样例输出 #1

6

数据范围

• 对于 $60\%$ 的数据，$3 \le n \le 300$；
• 对于 $100\%$ 的数据，$3 \le n \le 10^6$，$0 \le a_i, b_i \le 10^9$。

知识点与难度

本题涉及的知识点从属于 GESP 七级（最大流、三分搜索、贪心），难度等级：⭐⭐⭐⭐。

测试点分布