E. 翻转
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

给定两个长度为$$$n$$$的整数序列$$$a$$$，$$$b$$$。你可以最多一次翻转序列$$$a$$$的一个区间，最小化$$$\sum_{i=1}^{n}{a_i\oplus{b_i}}$$$。

所谓翻转区间$$$[l,r]$$$，就是$$$a=\{a_1,~a_2,~\ldots,~a_l,~\ldots,a_r,~\ldots,~a_n\}$$$，翻转以后变为$$$a_1,~a_2,~\ldots,~a_r,~a_{r-1},~\ldots,~a_{l+1},~a_l,~\ldots,~a_n$$$。

表达式 $$$x\oplus{y}$$$表示对$$$x$$$与$$$y$$$二进制表示下按位异或的结果。

Input

第一行输入单个整数 $$$n(1\leq{n}\leq{5000})$$$。

第二行输入$$$n$$$个整数 $$$a_1,a_2,\cdots,a_n$$$，代表序列 $$$a,~(1\leq{a_i}\leq{10^9})$$$。

第三行输入$$$n$$$个整数 $$$b_1,b_2,\cdots,b_n$$$，代表序列 $$$b,~(1\leq{b_i}\leq{10^9})$$$。

Output

输出一个整数，表示$$$\sum_{i=1}^{n}{a_i\oplus{b_i}}$$$的最小值。

Examples
Input
5
1 2 3 4 5
1 4 3 2 5
Output
0
Input
5
3 6 9 1 6
5 2 6 2 2
Output
20
Input
3
15 84 28
29 44 94
Output
76
Input
10
13 71 26 93 100 78 80 90 42 62
37 6 78 32 33 57 84 71 2 53
Output
416
Note

样例$$$1$$$选择反转区间 $$$[2,4]$$$ 后，序列$$$a$$$变为 $$$1,4,3,2,5$$$ 。此时$$$\sum_{i=1}^{n}{a_i\oplus{b_i}}=0$$$，显然这个是最小的。

样例$$$2$$$选择反转区间 $$$[1,4]$$$ 后，序列$$$a$$$变为 $$$1,9,6,3,6$$$ 。此时$$$\sum_{i=1}^{n}{a_i\oplus{b_i}}=20$$$，可以证明这样操作是最优的。