题目描述

给你一个二分图，有一些个左部点。还有 $m$ 个右部点，编号为 $0$ 到 $m-1$。

对于每个左部点 $i$，有一个连边参数 $a_i$，表示其向所有满足 $\exist x\in \mathbb{N}, a_ix\equiv j \pmod m$ 的 $j$ 连接了一条边。

现在给出两个长度为 $n$ 的数组 $a_i,c_i$，表示存在 $c_i$ 个左部点的连边参数为 $a_i$，换句话说，这个图总共有 $\sum\limits_{i=1}^n c_i$ 个左部点，使用这样的方式来快速读入左部点的连边参数。

保证 $a_i$ 两两不同。

求这张二分图的最大匹配。

输入格式

第一行两个整数 $n$ 和 $m$。

接下来 $n$ 行，每行两个正整数，第 $i$ 行的两个数分别表示 $a_i$ 和 $c_i$ 的值。

输出格式

一行一个整数，表示答案。

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

提示

本题采用捆绑测试。

Subtask	$n\le$	$m\le$	特殊性质	分数
0	$10^3$		无	10
1	$1$	$10^{12}$
2	$2 \times 10^3$	$2\times 10^7$	有	20
3			无
4		$10^{12}$	有
5	$7 \times 10^3$		无

对于所有数据，保证 $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}$

特殊性质 : 保证 $\mu(m)\not=0$。

其中 $\mu$ 指莫比乌斯函数，定义为

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

对于所有数据，保证 $a_i$ 互不相同。