JOI quyết định ăn tiểu long bao cho bữa trưa tại một nhà hàng Trung Hoa. Tiểu long bao là món ăn có nhân và nước súp nóng được bọc trong một lớp vỏ bột mì, nổi tiếng vì nước súp có thể bắn ra xung quanh khi ăn.

Phần ăn JOI gọi gồm \(N\) chiếc tiểu long bao có nhân hoặc nước súp khác nhau. Các chiếc bánh được xếp cách đều nhau trên một hàng, đánh số theo thứ tự từ \(1\) đến \(N\). Khoảng cách giữa chiếc bánh thứ \(i\) và chiếc bánh thứ \(j\) là \(|i - j|\).

JOI sẽ ăn các chiếc bánh theo một thứ tự nào đó. Ban đầu, độ ngon của tất cả các chiếc bánh đều bằng \(0\). Khi JOI ăn chiếc bánh thứ \(i\), nước súp của nó bắn ra xung quanh và rơi lên những chiếc bánh chưa được ăn nằm cách bánh \(i\) không quá \(D_i\). Độ ngon của mỗi chiếc bánh bị nước súp bắn trúng tăng thêm \(A_i\).

Cụ thể, khi chiếc bánh thứ \(i\) được ăn, nếu chiếc bánh thứ \(j\) vẫn chưa được ăn và thỏa mãn \(1 \le j \le N\), \(i - D_i \le j \le i + D_i\), thì độ ngon của chiếc bánh thứ \(j\) tăng thêm \(A_i\).

JOI muốn chọn thứ tự ăn sao cho tổng độ ngon của các chiếc bánh tại thời điểm ăn chúng là lớn nhất. Hãy viết chương trình tìm tổng độ ngon lớn nhất khi JOI ăn hết các chiếc bánh theo thứ tự tốt nhất.

Dữ liệu vào

Dữ liệu vào gồm \(3\) dòng:

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(D_1, D_2, \ldots, D_N\), cách nhau bởi dấu cách.
• Dòng thứ ba chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\), cách nhau bởi dấu cách.

Dữ liệu ra

In ra một dòng chứa tổng độ ngon lớn nhất của các chiếc bánh mà JOI ăn.

Ràng buộc

• \(1 \le N \le 100\).
• \(0 \le D_i \le 7\) với mọi \(1 \le i \le N\).
• \(0 \le A_i \le 1000\) với mọi \(1 \le i \le N\).

Ví dụ

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