
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 ith treasure point is in (x_{i}, y_{i}) if we put the map in 2Dplane. 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 x_{i} AND y_{i} (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. InputInput 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 x_{i} and y_{i} which represent the position of the point i. (1 ≤ N ≤ 500, 2≤ P≤ 10^{9}, 0 ≤ x_{i}, y_{i} ≤ 10^{9}, ∀ i,j, x_{i}⊕ y_{i}⊕ x_{j}⊕ y_{j}> 0) OutputPlease output the corresponding maximal total value, one line for one case. Sample Input3 4 1 2 2 4 1 3 Sample Output1 Author: LIN, Xi Source: ZOJ Monthly, March 2014 