Problem Description

You are given a bipartite graph with some left-side vertices and $m$ right-side vertices, numbered from $0$ to $m-1$.

For each left-side vertex $i$, there is an edge parameter $a_i$, meaning it connects to every $j$ such that $\exist x\in \mathbb{N}, a_ix\equiv j \pmod m$.

Now you are given two arrays $a_i, c_i$ of length $n$, meaning there are $c_i$ left-side vertices whose edge parameter is $a_i$. In other words, this graph has a total of $\sum\limits_{i=1}^n c_i$ left-side vertices. This is a fast way to input the edge parameters of the left-side vertices.

It is guaranteed that all $a_i$ are pairwise distinct.

Find the maximum matching of this bipartite graph.

Input Format

The first line contains two integers $n$ and $m$.

In the next $n$ lines, each line contains two positive integers. On the $i$-th line, the two numbers are $a_i$ and $c_i$.

Output Format

Output one integer in one line, which is the answer.

3 6
1 1
2 2
3 1

4

6 12
12 3
3 1
2 1
6 2
4 2
1 2

8

11 60
4 1
15 10
3 1
20 3
2 2
30 2
6 4
10 5
5 3
60 5
12 14

23

Hint

This problem uses bundled subtasks.

Subtask	$n\le$	$m\le$	Special Property	Score
0	$10^3$		None	10
1	$1$	$10^{12}$
2	$2 \times 10^3$	$2\times 10^7$	Yes	20
3			None
4		$10^{12}$	Yes
5	$7 \times 10^3$		None

For all testdata, it is guaranteed that $1\le n \le 7\times10^3, 1\le m \le 10^{12},1\le a_i \le m,0\le c_i \le 10^{12}$.

Special property: it is guaranteed that $\mu(m)\not=0$.

Here $\mu$ is the Möbius function, defined as

$$\mu(n)=\left\{\begin{array}{ll} 1 & n=1 \\ 0 & n \text { 含有平方因子 } \\ (-1)^{k} & k \text { 为 } n \text { 的本质不同质因子个数 } \end{array}\right.$$

For all testdata, it is guaranteed that all $a_i$ are pairwise distinct.

Translated by ChatGPT 5