← 返回题目列表

Codeforces · 631/A

A. 采访

中文机器翻译题面 查看原题

Blake 是一家名为“Blake Technologies”的大公司的首席执行官。他非常热爱他的公司,他认为他的公司应该是最好的。这就是为什么每个候选人都需要通过包含以下问题的面试。

我们将函数 f(x, l, r) 定义为整数 xl, xl + 1, ..., xr 的按位或,其中 xi 是数组 x 的第 i 个元素。给定两个长度为 n 的数组 a 和 b。您需要在所有可能的 1 ≤ l ≤ r ≤ n 中确定和 f(a, l, r) + f(b, l, r) 的最大值。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 1000) — 数组的长度。

第二行包含 n 个整数 ai (0 ≤ ai ≤ 109)。

第三行包含n个整数bi (0 ≤ bi ≤ 109)。

输出

打印单个整数 - 所有可能的 1 ≤ l ≤ r ≤ n 中 f(a, l, r) + f(b, l, r) 之和的最大值。

示例

输入 #1

5
1 2 4 3 2
2 3 3 12 1

输出 #1

22

输入 #2

10
13 2 7 11 8 4 9 8 5 1
5 7 18 9 2 3 0 11 8 6

输出 #2

46

注意

两个非负整数 a 和 b 的按位或为数字 c = a OR b,当且仅当 a 或 b 中至少有一个在二进制表示的相应位置上有 1 时,其二进制表示的每位数字均为 1。

在第一个示例中,最佳答案之一是 l = 2 和 r = 4,因为 f(a, 2, 4) + f(b, 2, 4) = (2 OR 4 OR 3) + (3 OR 3 OR 12) = 7 + 15 = 22。获得最大值的其他方法是选择 l = 1 和 r = 4, l = 1 和 r = 5, l = 2 且 r = 4、l = 2 且 r = 5、l = 3 且 r = 4,或 l = 3 且 r = 5。

在第二个示例中,当 l = 1 且 r = 9 时获得最大值。