Programming Duel Tournament

Time limit2sMemory limit256 MB

Summary

Choose a duel schedule for N contestants, where the higher skill always wins and each contestant duels at most L_i times, to maximize total duel XOR interest minus fatigue.

Level: Hard8 of 10
Topics: Greedy, Tree, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

Onjo runs a programming duel tournament with $N$ contestants. The tournament is $N-1$ duels, each one between two contestants. Contestant $i$ has skill $A_i$ , and no two contestants have the same skill. When two contestants duel, the one with the higher skill wins, and the loser is eliminated and duels no more. Each duel eliminates one contestant, so after $N-1$ duels a single contestant is left, and that contestant is the champion.

A duel between a contestant of skill $x$ and a contestant of skill $y$ has interest $x \oplus y$ , where $\oplus$ is bitwise XOR. Contestant $i$ gains $H_i$ fatigue for every duel they take part in, so a contestant who duels $k$ times ends with total fatigue $H_i \times k$ . Contestant $i$ can duel at most $L_i$ times.

The fun of the tournament is the total interest of all duels minus the total fatigue of all contestants. The fun can be negative. Who meets whom, and in what order, changes the fun.

For example, take three contestants with skills $1$ , $3$ , $5$ , with $H$ equal to $6$ , $2$ , $4$ and $L$ equal to $2$ , $2$ , $2$ . First contestant 1 duels contestant 2. Contestant 2 has the higher skill and wins, so contestant 1 is eliminated, and the interest of that duel is $A_1 \oplus A_2 = 1 \oplus 3 = 2$ . Then contestant 2 duels contestant 3. Contestant 3 wins and contestant 2 is eliminated, and the interest of that duel is $A_2 \oplus A_3 = 3 \oplus 5 = 6$ . The total interest is $2 + 6 = 8$ . The three contestants dueled 1, 2 and 1 times, so the total fatigue is $6 \times 1 + 2 \times 2 + 4 \times 1 = 14$ , and the fun is $8 - 14 = -6$ . Nobody dueled more than $L_i$ times, so every condition holds, and no schedule reaches a larger fun.

Given $N$ , $A_1$ through $A_N$ , $H_1$ through $H_N$ , and $L_1$ through $L_N$ , find the largest fun the tournament can reach while every condition holds.

Input

The first line has the number of contestants $N$ . ( $2 \le N \le 300$ )

The second line has $N$ integers $A_1$ through $A_N$ , separated by spaces. ( $1 \le A_i \le 10^6$ ) All $A_i$ are distinct.

The third line has $N$ integers $H_1$ through $H_N$ , separated by spaces. ( $1 \le H_i \le 10^6$ )

The fourth line has $N$ integers $L_1$ through $L_N$ , separated by spaces. ( $2 \le L_i \le N-1$ )

Output

Print the largest fun the tournament can reach while every condition holds.

Examples3

Example 1
Input
```
3
1 3 5
6 2 4
2 2 2
```
Expected output
```
-6
```
Example 2
Input
```
3
2 4 8
1 1 1
2 2 2
```
Expected output
```
18
```
Example 3
Input
```
4
1 2 3 4
5 5 5 5
2 2 2 2
```
Expected output
```
-14
```