샤오룽바오

문제

JOI 군은 점심으로 중국집에서 샤오룽바오를 먹기로 했다. 샤오룽바오란 속재료와 뜨거운 육수를 밀가루 피로 감싼 요리로, 먹을 때 육수가 주위로 튀는 것으로 알려져 있다.

JOI 군이 주문한 샤오룽바오 세트는 속재료와 육수가 서로 다른 N개의 샤오룽바오로 이루어져 있다. N개의 샤오룽바오는 같은 간격으로 한 줄로 늘어서 있으며, 순서대로 1부터 N까지의 번호가 붙어 있다. i번째 샤오룽바오와 j번째 샤오룽바오 사이의 거리는 절댓값 |i - j| 이다.

JOI 군은 샤오룽바오를 어떤 순서로 먹어 나간다. 처음에 모든 샤오룽바오의 맛있음은 0이다. i번째 샤오룽바오를 먹으면 주위로 그 국물이 튀어, 아직 먹지 않은 샤오룽바오 중 샤오룽바오 i로부터의 거리가 $D_{i}$ 이하인 샤오룽바오에 국물이 묻는다. 국물이 묻은 샤오룽바오는 맛있음이 $A_{i}$ 만큼 늘어난다. 즉, i번째 샤오룽바오를 먹었을 때 j번째 샤오룽바오 (1 ≦ j ≦ N 이고 i - $D_{i}$ ≦ j ≦ i + $D_{i}$) 가 아직 먹히지 않고 남아 있다면, j번째 샤오룽바오의 맛있음이 $A_{i}$ 만큼 늘어난다.

JOI 군은 먹는 순서를 잘 정해서, 먹는 샤오룽바오의 맛있음의 합계를 최대화하고 싶다. 가장 좋은 순서로 먹었을 때 JOI 군이 먹는 샤오룽바오의 맛있음의 합계를 구하는 프로그램을 작성하시오.

입력

입력 파일은 3개의 줄로 이루어진다.

1번째 줄에는 1개의 정수 N (1 ≦ N ≦ 100) 이 쓰여 있다.

2번째 줄에는 N개의 정수 $D_{1}$, $D_{2}$, ..., $D_{N}$ (0 ≦ $D_{i}$ ≦ 7) 이 공백으로 구분되어 쓰여 있다.

3번째 줄에는 N개의 정수 $A_{1}$, $A_{2}$, ..., $A_{N}$ (0 ≦ $A_{i}$ ≦ 1000) 이 공백으로 구분되어 쓰여 있다.

출력

JOI 군이 먹는 샤오룽바오의 맛있음의 합계의 최댓값을 1개의 줄에 출력한다.

예제 입력 1

5
1 0 1 1 2
0 2 6 3 4

예제 출력 1

20

예제 1에서는 5번째 → 3번째 → 1번째 → 2번째 → 4번째 의 순서로 먹으면 맛있음의 합계가 20이 된다. 합계가 20을 넘는 먹는 방법은 존재하지 않으므로, 이것이 최선이다.

예제 입력 2

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

예제 출력 2

237