2023 年 “图森未来杯” 全国高校程序设计网络邀请赛

I. 宝箱

单点时限: 1.0 sec

内存限制: 256 MB

Cuber QQ 的《弈!悟!》一上线就成为了爆款手游。为了留住更多的活跃用户,Cuber QQ 准备设计一些奖励机制,吸引用户每天按时登陆游戏。

Cuber QQ 推出了一场 n 天打卡活动,玩家每天登陆游戏就可获得一个红色宝箱和一个蓝色宝箱。红色宝箱和蓝色宝箱中均可开出一定数额的金币(金币数额一定是正整数)。而且随着连续打卡天数的增加,奖励会越加丰厚。在第 i+1 天的红色宝箱中开出的金额一定高于第 i 天的红色宝箱。同样地,第 i+1 天的蓝色宝箱中开出的金额一定高于第 i 天的蓝色宝箱。

核心玩家们肯定不会错过每一天的宝箱,一个全勤的玩家可以获得全部的 2n 个宝箱。Cuber QQ 为了给玩家一点惊喜,他想,这所有的 2n 个宝箱中的金币数应当互不相同;而且他想指定这其中某几个箱子一定会开出奇数数目的金币,其余的箱子一定会开出偶数数目的金币。

当然,Cuber QQ 也不想让玩家在一个箱子中获得太多的金币。他想问问你,在满足这些要求的前提下,如何安排每个宝箱开出的数额,可以使得一个玩家在单个宝箱中获得的金币的最大值尽可能小。

输入格式

第一行包含一个整数 n1n1000),表示登陆活动的天数。

第二行包含 n 个整数 a1,a2,,aiai=0 表示第 i 天的红色宝箱一定开出偶数枚金币,ai=1 表示第 i 天的红色宝箱一定会开出奇数枚金币。

第三行包含 n 个整数 b1,b2,,bibi=0 表示第 i 天的蓝色宝箱一定开出偶数枚金币,bi=1 表示第 i 天的蓝色宝箱一定会开出奇数枚金币。

输出格式

输出共一行,包含一个整数,表示一个玩家在单个宝箱中获得的最多的金币数的最小值。

样例

Input
5
1 0 0 1 1
0 0 0 1 0
Output
12

提示

在样例所述的情况中,我们可以让每天的红色宝箱分别开出 1、2、4、5、7 枚金币,每天的蓝色宝箱分别开出 6、8、10、11、12 枚金币,这样玩家在单个宝箱中最多获得 12 个金币。在其他的方案中,玩家在单个宝箱中开出的金币数的最大值都不会小于 12。