小分图最大匹配

给你一个二分图，有一些个左部点。还有 $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^3$ | 无 | 10 | | 1 | $1$ | $10^{12}$ | 无 | 10 | | 2 | $2 \times 10^3$ | $2\times 10^7$ | 有 | 20 | | 3 | $2 \times 10^3$ | $2\times 10^7$ | 无 | 20 | | 4 | $2 \times 10^3$ | $10^{12}$ | 有 | 20 | | 5 | $7 \times 10^3$ | $10^{12}$ | 无 | 20 | 对于所有数据，保证 $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$ 互不相同。