ZOJ Problem Set - 3760
George is eager about treasure hunting. One day, he got a treasure map from God (It's the welfare from God for some people).
There are N treasure points on the map. And the i-th treasure point is in (xi, yi) if we put the map in 2D-plane. God told George that he could choose some of the treasure points and got the treasure there. The value of treasure in point i is xi AND yi (in C/C++ AND means &, in Pascal AND means and). But the set (let's use T to represent it) of treasure points George chose must satisfy the following condition:
George want to maximize the total value he got from the treasure points he chose.
Input will consist of multiple test cases and each case will consist of two lines. For each test case the program has to read the integers N and P, separated by a blank, from the first line. The next N lines each contain two integers xi and yi which represent the position of the point i. (1 ≤ N ≤ 500, 2≤ P≤ 109, 0 ≤ xi, yi ≤ 109, ∀ i,j, xi⊕ yi⊕ xj⊕ yj> 0)
Please output the corresponding maximal total value, one line for one case.
3 4 1 2 2 4 1 3
Author: LIN, Xi
Source: ZOJ Monthly, March 2014