P10918 Maximum Matching in a Small-Partition Bipartite Graph

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.

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 one integer in one line, which is the answer.

**This problem uses bundled subtasks**. | Subtask | $n\le$ | $m\le$ | Special Property | Score | | :-: | :--------: | :-: | :-: | :-: | | 0 | $10^3$ | $10^3$ | None | 10 | | 1 | $1$ | $10^{12}$ | None | 10 | | 2 | $2 \times 10^3$ | $2\times 10^7$ | Yes | 20 | | 3 | $2 \times 10^3$ | $2\times 10^7$ | None | 20 | | 4 | $2 \times 10^3$ | $10^{12}$ | Yes | 20 | | 5 | $7 \times 10^3$ | $10^{12}$ | None | 20 | 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