Welcome to ZOJ
Select Problem
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 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)


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

    Sample Input

    3 4
    1 2
    2 4
    1 3

    Sample Output


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