绝美的挣扎

题目背景

彗星已经分裂,留给三叶的时间不多了。三叶的父亲当机立断,决定以演习的名义疏散全镇居民;然而,糸守湖畔有许多危险设施,必须在彗星落下前妥善处置。为了让更多的人幸存,你能帮助三叶处理好这些设施吗?

题目描述

本题中将彗星落下前的糸守湖视为圆形。在糸守湖畔均匀分布着$n$个危险设施,将它们按顺序编号为$1,2,\cdots,n$,如下图。 ![编号示意](https://cdn.luogu.com.cn/upload/pic/31558.png) 定义两个设施间的距离为连接这两个设施的圆弧中较短的一条的长度,把相邻两设施的距离定义为$1$单位距离。如上图中,$1$号设施与$2$号设施间的距离为$1$,$1$号设施与$3$号设施的距离为$2$,$1$号设施与$5$号设施的距离为$4$,$1$号设施与$6$号设施的距离为$3$。 这些设施之间存在相互干扰关系,这导致如果控制某一个设施,就不能控制与它距离较近的其他设施。具体地说,每一个设施有一个干扰度$k_{i}(1\le i \le n)$,如果控制$i$号设施,那么就不能控制与$i$号设施的距离**不大于**$k_{i}$的其他设施。例如,在上图中若$k_{1}=2$,则如果控制$1$号设施,就不能控制$2$号、$3$号、$7$号和$8$号设施。 不同设施的危险程度不同。为了描述设施的危险程度,三叶根据相关资料为每个设施评定了危险度,$i$号设施的危险度为$w_{i}$。为了尽可能保障人民群众的生命安全,三叶希望控制的所有设施的危险度之和最大。 现在三叶想求出所能控制的所有设施的危险度之和的最大值,你能帮助她吗?

输入输出格式

输入格式


输入共$3$行。 第$1$行有一个正整数$n$,表示危险设施的数目。 第$2$行有$n$个以空格分隔的正整数,第$i$个正整数$w_{i}$表示$i$号设施的危险度。 第$3$行有$n$个以空格分隔的非负整数,第$i$个非负整数$k_{i}$表示$i$号设施的干扰度。

输出格式


输出共$1$行,包含$1$个非负整数,表示所能控制的所有设施的危险度之和的最大值。

输入输出样例

输入样例 #1

5
8 10 9 10 7
2 0 3 1 2

输出样例 #1

20

输入样例 #2

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

输出样例 #2

21

输入样例 #3

10
8 7 9 3 2 10 8 7 6 6
0 10 2 6 9 8 3 8 6 9

输出样例 #3

17

说明

对于10%的数据,满足$n\le 20, k_{i}\le 20$。 对于另外10%的数据,满足$n\le 70,k_{i} \le 20$。 对于另外10%的数据,满足$k_{i}=0$。 对于另外10%的数据,满足$k_{i}=1$。 对于100%的数据,满足$n\le 1000, k\le 50, w_{i}\le 10^{6}, k \le n$。 ![数据范围表](https://cdn.luogu.com.cn/upload/pic/35605.png) ------ 样例$1$解释:控制$2,4$号设施。 样例$2$解释:控制$1,3,6$号设施。 样例$3$解释:控制$3,7$号设施。