题目背景

JOI同学的午饭，是在中华料理店买的小笼包。这是一种用小麦粉制成的皮包着馅和热汤的料理，吃的时候，热汤会飞溅出来。

题目描述

JOI 同学点的小笼包套餐，由馅料不同的 $N$ 个小笼包组成。$N$ 个小笼包等间隔排成一列，编号为 $1$ 到 $N$。第 $i$ 个小笼包与第 $j$ 个小笼包之间的距离是绝对值 $\vert i - j \vert$。 JOI 同学按照顺序吃小笼包。最初，所有的小笼包的美味度都是 $0$。吃第 $i$ 个小笼包时，汤汁向周围飞散，与第 $i$ 个小笼包距离 $D_i$ 以下的小笼包都淋上了汤汁，而被淋上汤汁的小笼包的美味度会增加 $A_i$。也就是说，吃第 $i$ 个小笼包的时候，第 $j$ 个小笼包 $(1 \leq j \leq N$ 并且 $i - D_i \leq j \leq i + D_i)$ 还没有吃到的话，第 $j$ 个小笼包的美味度就增加 $A_i$。

JOI 同学要在吃小笼包的顺序上下功夫，让吃的小笼包的美味度的合计最大化。

输入格式

输入共 $3$ 行。

第 $1$ 行是 $1$ 个整数 $N$。

第 $2$ 行是 $N$ 个整数 $D_1,D_2,...,D_N (0 \leq D_i \leq 7)$，以空格分隔。

第 $3$ 行是 $N$ 个整数 $A_1,A_2,...,A_N (0 \leq A_i \leq 1000)$，以空格分隔。

输出格式

共 $1$ 行，输出 JOI 同学吃的小笼包的美味度的合计最大值。

5
1 0 1 1 2
0 2 6 3 4

20

10
5 2 7 2 6 5 3 5 3 6
8 7 8 4 0 6 0 10 10 0

237

提示

样例 $1$ 的说明：以第 $5 \rightarrow$ 第 $3 \rightarrow$ 第 $1 \rightarrow$ 第 $2 \rightarrow$ 第 $4$ 的顺序吃的话，美味度合计为 $20$，因为美味度超过 $20$ 的吃法是不存在的，所以这是最好的。

本题是 2014 年日本信息学奥林匹克（JOI）预选第 6 题。