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 时获得最大值。