리본

가로로 있는 막대에 $N$ 개의 리본이 매달려 있다. $i$ 번째 리본은 막대의 왼쪽 끝에서 거리 $X_i$인 곳에 매달려 있고 길이는 $A_i$이며, 가중치는 $B_i$이다.

각 리본에 대해서 할 수 있는 선택은 두 가지이다.

1. 리본을 다른 리본 하나와 묶을 수 있다. $i$ 번째 리본을 $j$ 번째 리본과 묶으면 각진 'U'자 모양이 된다. 즉, 직사각형의 왼쪽, 아래, 오른쪽 세 변과 같은 모양이다. 직사각형의 가로는 길이 $|X_j - X_i|$이고 세로는 길이 $(A_i + A_j - |X_j - X_i|)/2$가 된다. 세로 길이가 음수가 아닌 경우만 묶는 것이 가능하다. 세로 길이가 $0$인 경우 묶인 리본은 막대에 붙어 있다. 편의상 두 리본을 묶으면서 생기는 매듭이 매우 작아, 그로 인해 줄어드는 길이는 없다고 하자.
2. 리본을 다른 리본과 묶지 않고 그대로 둔다. 이 경우 리본은 똑바로 아래로 내려져 있다.

모든 선택을 다 마치고 묶을 리본들을 다 묶었을 때, 어떤 리본 쌍도 공유하는 점이 있는 것은 허용되지 않는다.

아래 그림의 경우는 허용이 되는 경우이다.

아래 그림의 경우는 $4$ 개의 리본들에서 왼쪽에서 첫 번째와 네 번째 리본을 묶고, 두 번째와 세 번째 리본을 묶은 것인데, 묶인 리본 쌍이 교차하므로 허용되지 않는 모양이다.

좀 더 구체적인 예로, $N = 3$이고 각 리본의 막대 왼쪽 끝에서 거리가 $1$, $2$, $3$이고, 길이가 $2$, $1$, $2$일 때, 첫 번째와 세 번째 리본을 묶고 두 번째 리본을 그대로 두면 아래 그림과 같이 두 번째 리본의 끝이 묶인 리본 쌍에 닿게 되어 허용되지 않는 모양이다. 그림에서 두 번째 리본은 붉은색으로 표현하였다.

또, $N = 4$이고 각 리본의 막대 왼쪽 끝에서 거리가 $1$, $2$, $3$, $4$이고, 길이가 $3$, $1$, $2$, $2$일 때, 첫 번째와 네 번째 리본을 묶고 두 번째와 세 번째 리본을 묶으면 두 리본 쌍의 가로 부분이 겹치게 되어 역시 허용되지 않는 모양이다.

모든 선택을 다 마치고 묶을 리본들을 다 묶었을 때 $i$ 번째와 $j$ 번째 리본을 묶은 쌍에 대해서 점수는 $B_i \times B_j$이다. $i$ 번째 리본을 묶지 않은 경우 점수는 $B_i$이다.

적절한 선택을 하여 점수 합의 최댓값을 구하는 프로그램을 작성하시오.

입력 형식

첫 줄에 리본의 개수 $N$이 주어진다. ($1 \le N \le 150$)

두 번째 줄에 각 리본의 막대 왼쪽 끝에서의 거리를 나타내는 $N$ 개의 정수 $X_1, X_2, \cdots, X_N$이 공백으로 구분되어 주어진다. ($1 \le X_1 < X_2 < \cdots < X_N \le 1\,000\,000\,000$)

세 번째 줄에 각 리본의 길이를 나타내는 $N$ 개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 1\,000\,000\,000$)

네 번째 줄에 각 리본의 가중치를 나타내는 $N$ 개의 정수 $B_1, B_2, \cdots, B_N$이 공백으로 구분되어 주어진다. ($1 \le B_i \le 100\,000\,000$)

출력 형식

첫 줄에 점수 합의 최댓값을 출력한다.

예제

3
1 2 3
2 1 2
5 2 4

14

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설