문제

마법 공연이 끝난 뒤, 무대 주위에는 $N$마리의 슬라임이 일렬으로 서 있다.

각 슬라임은 색깔을 나타내는 정수 $C_i$를 가진다.

봉사시간을 채우기 위해 청소 봉사를 하게 된 지원이는 무대 위 슬라임을 모두 제거해야 한다.

한 번의 행동으로, 현재 무대에서 서로 연속해 있고 같은 색인 슬라임들만으로 이루어진 구간 하나를 골라 구간의 일부 혹은 전체를 제거할 수 있다.

길이가 $x$ 인 구간을 제거하면 관객석 청소 점수 $P_x$ 를 얻는다.

슬라임을 제거하면 양옆의 슬라임들이 서로 붙게 되어, 이전에는 떨어져 있던 두 구간이 새롭게 이웃하게 될 수 있다.

모든 슬라임을 제거했을 때 얻을 수 있는 최대 점수를 구하여라.

입력

첫째 줄에 슬라임의 수 $N$이 주어진다.

둘째 줄에 $P_1, P_2, \cdots , P_N$ 이 주어진다.

셋째 줄에 $C_1, C_2, \cdots , C_N$ 이 주어진다.

$1 \leq N \leq 100$

$1 \leq P_x \leq 10^{12}$

$1 \leq C_i \leq 10^9$

출력

모든 슬라임을 제거했을 때 얻을 수 있는 최대 점수를 출력한다.

예제 입력 1

5
1 5 6 10 20
1 2 1 1 2

예제 출력 1

11