405065: GYM101773 E Max $\mathcal{B}$-Matching

Max is an expert in combinatorial optimization and bitwise operations. He recently read a paper about so-called b-matchings, but it appeared to be too complicated and unnatural for him, so he decided to create his own kind of matchings and to call it -matching. He came up with a following problem.

Recall that the bitwise AND of two non-negative integers x and y is such a number x & y that it has ones in a binary representation in exactly those positions, in which both x and y also have ones in a binary representation. Define a function to be equal to a largest power of two not exceeding z if z is positive and to zero if z = 0.

You are given a complete bipartite graph (i.e. such bipartite graph that any two vertices from different parts are connected with an edge). Vertices of the first part of the graph are numbered from 1 to n₁, vertices of the second part of the graph are numbered from 1 to n₂. The i-th vertex of the first part of the graph is assigned a non-negative integer x_i, the j-th vertex of the second part of the graph is assigned a non-negative integer y_j.

Recall that the matching in a graph is such a set M of edges that no two distinct edges share a common endpoint. Define a weight of an edge connecting vertices u and v (from the first part and the second part of a graph respectively) to be (that is why it is valid to call such an object -matching in the future!)

Your task is to find a matching of a maximum possible total weight of edges.

The first line of input contains two integers n₁ and n₂ (1 ≤ n₁, n₂ ≤ 100 000).

The second line of input contains n₁ integers x₁, x₂, ..., x_n1 (0 ≤ x_i < 2²⁰) that are assigned to the corresponding vertices of the first part of the graph.

The third line of input contains n₂ integers y₁, y₂, ..., y_n2 (0 ≤ y_i < 2²⁰) that are assigned to the corresponding vertices of the second part of the graph.

Output the maximum possible total weight of edges of a matching in a given graph.

4 5
5 7 5 2
1 2 3 4 2

9

In the sample test the best possible matching consists of edges (1, 1), (2, 5), (3, 4) and (4, 3) (where the first number in pair denotes the index of a vertex of a first part, and the second number denotes the index of a vertex of a second part).