AT_abc291_g [ABC291G] OR Sum

[problemUrl]: https://atcoder.jp/contests/abc291/tasks/abc291_g 長さ $ N $ の数列 $ A=(A_0,A_1,\ldots,A_{N-1}) $ と $ B=(B_0,B_1,\ldots,B_{N-1}) $ が与えられます。 また、高橋君は数列 $ A $ に対して、次の操作を好きな回数 ( $ 0 $ 回でもよい) 行う事ができます。 - $ A $ を $ 1 $ つ左にシフトする、すなわち、$ A $ を、$ A'_i=A_{(i+1)\%\ N} $ で定義される $ A' $ で置き換える。ただし、$ x\%\ N $ で、$ x $ を $ N $ で割った余りを表す。 高橋君の目的は $ \displaystyle\sum_{i=0}^{N-1}\ (A_i|B_i) $ を最大化することです。ただし、$ x|y $ で $ x $ と $ y $ のビット毎の論理和(bitwise OR)を表します。 $ \displaystyle\sum_{i=0}^{N-1}\ (A_i|B_i) $ の値としてあり得る最大の値を求めてください。 ビット毎の論理和(bitwise OR)とは $ 1 $ ビットの数字 ($ 0 $ または $ 1 $) の組に対して下の表で定義される演算を**論理和**（またはOR演算）といいます。 ビット毎に論理和を適用する演算を**ビット毎の論理和（bitwise OR）**といいます。 $ 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

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 5\times\ 10^5 $ - $ 0\leq\ A_i,B_i\ \leq\ 31 $ - 入力はすべて整数 ### Sample Explanation 1 高橋君が一度も操作を行わなかった時、$ A $ は $ (0,1,3) $ のままであり、$ \displaystyle\sum_{i=0}^{N-1}\ (A_i|B_i)=(0|0)+(1|2)+(3|3)=0+3+3=6 $, 高橋君が $ 1 $ 回操作を行った時、$ A=(1,3,0) $ となり、$ \displaystyle\sum_{i=0}^{N-1}\ (A_i|B_i)=(1|0)+(3|2)+(0|3)=1+3+3=7 $, 高橋君が $ 2 $ 回操作を行った時、$ A=(3,0,1) $ となり、$ \displaystyle\sum_{i=0}^{N-1}\ (A_i|B_i)=(3|0)+(0|2)+(1|3)=3+2+3=8 $ となります。$ 3 $ 回以上操作を行った時、 $ A $ は上記のいずれかの形になるため、$ \displaystyle\sum_{i=0}^{N-1}\ (A_i|B_i) $ の最大値は $ 8 $ であり、$ 8 $ を出力します。 ### Sample Explanation 2 最大となるのは高橋君が $ 3 $ 回操作を行った時であり、この時 $ 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 $ となります。