OR 求和

题目描述

有长度为 $N$ 的序列 $A=(A_0,A_1,\ldots,A_{N-1})$ 和 $B=(B_0,B_1,\ldots,B_{N-1})$。

高桥君可以对 $A$ 进行任意次(可能为 0 次)以下操作:

对序列 $A$ 进行一次左循环移位。即,用 $A'_i=A_{(i+1)\% N}$ 定义的 $A'$ 替换 $A$,其中 $x\% N$ 表示 $x$ 除以 $N$ 的余数。

高桥君的目标是最大化 $\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)$,其中 $x|y$ 表示 $x$ 和 $y$ 的按位逻辑和(按位或)。

求 $\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)$ 的最大可能值。

什么是按位逻辑和(按位或)?

逻辑和(或运算)是对两个一位整数(0 或 1)进行的运算,由下表定义。

按位逻辑和(按位或)是对每一位逐位应用逻辑和的运算。

| $x$ | $y$ | $x|y$ | | :---: | :---: | :---: | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 |

如果 $x$ 和 $y$ 的位中至少有一个为 1,则逻辑和结果为 1。 反之,仅当两个位都为 0 时,结果才为 0。

例:

0110 | 0101 = 0111

输入格式

输入按以下格式从标准输入给出：

$N$
$A_0$ $A_1$ $\ldots$ $A_{N-1}$
$B_0$ $B_1$ $\ldots$ $B_{N-1}$

输出格式

输出 $\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)$ 的最大可能值。

样例

3
0 1 3
0 2 3

8

如果高桥君不进行操作,$A$ 保持为 $(0,1,3)$,有 $\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(0|0)+(1|2)+(3|3)=0+3+3=6$;

如果进行一次操作,使 $A=(1,3,0)$,有 $\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(1|0)+(3|2)+(0|3)=1+3+3=7$;

如果进行两次操作,使 $A=(3,0,1)$,有 $\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(3|0)+(0|2)+(1|3)=3+2+3=8$。

如果进行三次及以上操作,$A$ 会变成上述序列之一,因此 $\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)$ 的最大值为 $8$,应输出 $8$。

5
1 6 1 4 3
0 6 4 0 1

23

进行三次操作使 $A=(4,3,1,6,1)$ 时,值最大,

此时 $\displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(4|0)+(3|6)+(1|4)+(6|0)+(1|1)=4+7+5+6+1=23$。

数据范围

• $2 \leq N \leq 5\times 10^5$
• $0\leq A_i,B_i \leq 31$
• 输入中的所有值均为整数。