프로그래밍 대결 대회

시간 제한2초메모리 제한256 MB

요약

N명의 참가자가 치르는 결투 일정을 정한다. 실력이 높은 쪽이 항상 이기고 각 참가자는 최대 L_i번 결투할 수 있을 때, 모든 결투의 XOR 관심도 합에서 피로도를 뺀 값이 최대가 되게 하라.

난이도: 어려움10점 중 8점
유형: 그리디, 트리, 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

온조는 $N$ 명이 참가하는 프로그래밍 대결 대회를 연다. 이 대회는 두 참가자가 일대일로 맞붙는 $N-1$ 번의 대결로 진행된다. $i$ 번 참가자의 실력은 $A_i$ 이고, 실력이 같은 참가자는 없다. 두 참가자가 대결하면 실력이 더 높은 쪽이 이기고, 진 쪽은 탈락해 더 이상 대결하지 못한다. 대결 한 번마다 한 명씩 탈락하므로 $N-1$ 번의 대결이 끝나면 한 명만 남고, 그 사람이 우승자가 된다.

실력이 $x$ 인 참가자와 실력이 $y$ 인 참가자가 맞붙은 대결의 흥미로움은 $x \oplus y$ 로 정의한다. 여기서 $\oplus$ 는 비트 단위 XOR이다. 한편 $i$ 번 참가자는 대결을 한 번 치를 때마다 피로도가 $H_i$ 만큼 쌓인다. 즉 $i$ 번 참가자가 대결을 $k$ 번 치렀다면 이 참가자의 총 피로도는 $H_i \times k$ 이다. 또 $i$ 번 참가자는 대결을 최대 $L_i$ 번까지만 치를 수 있다.

대회의 재미는 모든 대결의 흥미로움을 합한 값에서 모든 참가자의 피로도를 합한 값을 뺀 값이다. 대회의 재미는 음수가 될 수 있다. 누가 언제 누구와 맞붙느냐에 따라 대회의 재미가 달라진다.

예를 들어 실력이 각각 $1$ , $3$ , $5$ 이고 $H$ 가 각각 $6$ , $2$ , $4$ 이며 $L$ 이 각각 $2$ , $2$ , $2$ 인 참가자 세 명을 생각해 보자. 먼저 1번과 2번이 맞붙으면 실력이 더 높은 2번이 이기고 1번이 탈락한다. 이 대결의 흥미로움은 $A_1 \oplus A_2 = 1 \oplus 3 = 2$ 이다. 이어서 2번과 3번이 맞붙으면 3번이 이기고 2번이 탈락하며, 이 대결의 흥미로움은 $A_2 \oplus A_3 = 3 \oplus 5 = 6$ 이다. 흥미로움의 합은 $2 + 6 = 8$ 이고, 세 참가자가 치른 대결 수가 각각 1번, 2번, 1번이므로 피로도의 합은 $6 \times 1 + 2 \times 2 + 4 \times 1 = 14$ 이다. 따라서 대회의 재미는 $8 - 14 = -6$ 이다. 모든 참가자가 $L_i$ 번 이하로 대결했으니 조건도 지켰고, 이보다 재미를 크게 만드는 방법은 없다.

$N$ 과 $A_1$ 부터 $A_N$ , $H_1$ 부터 $H_N$ , $L_1$ 부터 $L_N$ 이 주어질 때, 조건을 모두 지키면서 얻을 수 있는 대회의 재미의 최댓값을 구하여라.

입력

첫째 줄에 참가자 수 $N$ 이 주어진다. ( $2 \le N \le 300$ )

둘째 줄에 $A_1$ 부터 $A_N$ 까지 $N$ 개의 정수가 공백으로 구분되어 주어진다. ( $1 \le A_i \le 10^6$ ) $A_i$ 는 모두 서로 다르다.

셋째 줄에 $H_1$ 부터 $H_N$ 까지 $N$ 개의 정수가 공백으로 구분되어 주어진다. ( $1 \le H_i \le 10^6$ )

넷째 줄에 $L_1$ 부터 $L_N$ 까지 $N$ 개의 정수가 공백으로 구분되어 주어진다. ( $2 \le L_i \le N-1$ )

출력

첫째 줄에 조건을 모두 지키면서 만들 수 있는 대회의 재미의 최댓값을 출력한다.

예제3

예제 1
입력
```
3
1 3 5
6 2 4
2 2 2
```
예상 출력
```
-6
```
예제 2
입력
```
3
2 4 8
1 1 1
2 2 2
```
예상 출력
```
18
```
예제 3
입력
```
4
1 2 3 4
5 5 5 5
2 2 2 2
```
예상 출력
```
-14
```