Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3760
Treasure Hunting

Time Limit: 3 Seconds      Memory Limit: 65536 KB

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:

• ∀ (xi, yi), (xj, yj) (i ≠ j) ∈ T, gcd(xiyixjyj, P)>1. P is an even integer God gave George and ⊕ means exclusive or.
• George want to maximize the total value he got from the treasure points he chose.

#### Input

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, xiyixjyj> 0)

#### Output

Please output the corresponding maximal total value, one line for one case.

#### Sample Input

3 4
1 2
2 4
1 3


#### Sample Output

1


Author: LIN, Xi
Source: ZOJ Monthly, March 2014
Submit    Status