Autores: Javier Oliva, Vicente Opazo

Tiempo límite: 2 segundos

Memoria límite: 256 megabytes

Nacho y Martín están en la fila para almorzar en el CIPC, pero esta fila está tomando una eternidad en avanzar. Tanto así que decidieron sentarse en el piso y jugar un juego.

Hay \(n\) fichas y cada ficha tiene dos valores \(x_{i}\) y \(a_{i}\). Nacho escogerá un subconjunto de estas fichas, denotado \(S\), con puntaje

\[S_{p}=\sum_{(x_{i},a_{i})\in S}a_{i}\]

la suma de los \(a_{i}\) escogidos.

Después, Martín tiene dos opciones, dejar el puntaje final en \(f= S_{p}\) o escoger un subconjunto \(M\) de las fichas escogidas por Nacho \(S\) y obtener un puntaje final igual a

\[f= S_{p}\times \bigoplus_{(x_{i},a_{i})\in M}x_{i}\]

donde \(\oplus ^{∗}\) se entiende como el operador binario XOR.

Nacho quiere maximizar el valor de \(f\) y Martín quiere minimizarlo. Si ambos juegan de manera óptima, ¿cuál será el puntaje final?

Nota

El operador binario \(\oplus\) trabaja sobre la representación binaria de sus operandos. Calcularemos \(10 \oplus 12\) como ejemplo.

La representación binaria de \(10\) es \((1010)_{2}\) y la representación binaria de \(12\) es \((1100)_{2}\).

\[1010 \oplus 1100\]

Vamos posición por posición (columna por columna) operando los bits de \(10\) y \(12\).

• \(0 \oplus 0 = 0\).
• \(0 \oplus 1 = 1\).
• \(1 \oplus 0 = 1\).
• \(1 \oplus 1 = 0\).

El último bit (o bit menos signitifativo) de \((1010)_{2}\) es \(0\) y el de \((1100)_{2}\) es \(0\). Entonces el bit menos significativo del resultado será \(0 \oplus 0 = 0\).

El siguiente bit (el penúltimo) de \((1010)_{2}\) es \(1\) y el de \((1100)_{2}\) es \(0\). Entonces el bit menos significativo del resultado será \(1 \oplus 0 = 1\).

Y seguimos así bit por bit y obtenemos

\[1010 \oplus 1100 = 0110\]

Y \((0110)_{2}\) es la representación binaria de \(6\). Entonces \(10 \oplus 12 = 6\).

Entrada

La primera línea contiene el entero \(n (1 \le n\le 10^{6})\) — el largo de la lista.

La segunda línea contiene \(n\) enteros \(x_{1}, x_{2}, \ldots , x_{n} (0 \le x_{i}\le 10^{18})\) — el primer valor de cada ficha.

La tercera línea contiene \(n\) enteros \(a_{1}, a_{2}, \ldots , a_{n} (0 \le a_{i}\le 10^{12})\) — el segundo valor de cada ficha.

entrada/salida rápida.

• En C++: al inicio del programa main deberán escribir std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
• En Java: usar BufferedReader con StringTokenizer para la entrada, y BufferedWriter o PrintWriter para la salida.
• En Python: usar sys.stdin.readline en lugar de input() y sys.stdout.write para la salida.

Salida

Imprime el puntaje final.

Ejemplos

Entrada 1

4
10 11 12 13
9 1 3 4

Salida 1

16

Entrada 2

3
8 4 2
10 9 11

Salida 2

30