P12966 [CCO 2025] Asteroid Mining

It is the year 2017 and Ryan is an asteroid miner. He makes a living by mining asteroids and selling them at the CCO (Celestial Cargo Outpost). On his latest mining expedition, he has mined $N$ mineral chunks where the $i$-th chunk has a value $v_i$ and a mass $m_i$. Ryan plans to transport a set of chunks to the CCO with his rocket, but he only has enough fuel to last one more trip. He calculated that the maximum total mass he can safely carry on his rocket is $M$. Due to Ryan's mining technique, the chunks exhibit a special property: for any two mineral chunks, one's mass is divisible by the other chunk's mass. Help Ryan find the maximum total value he can ship to CCO while adhering to his rocket's constraints.

The first line will contain two space-separated integers $N$ ($1 \leq N \leq 500000$) and $M$ ($1 \leq M \leq 10^{12}$). The next $N$ lines will each contain two space-separated integers $v_i$ ($1 \leq v_i \leq 10^{12}$) and $m_i$ ($1 \leq m_i \leq 10^{12}$), representing the value and mass of the $i$-th mineral chunk respectively. **Additionally, for any two mineral chunks $i, j$ ($1 \leq i, j \leq N$), either $m_i \mid m_j$ or $m_j \mid m_i$, where $a \mid b$ means that $a$ is a divisor of $b$ (i.e., $\frac{b}{a}$ is an integer).**

On one line, output one integer, the maximum total value Ryan can ship to CCO.

**Sample Explanation** Ryan can take all the chucks except the second and fifth chucks to achieve a total value of $1 + 200 + 9 + 100 = 310$. Note that the total mass of the chunks is $1 + 6 + 2 + 1 = 10$. We can show that this is optimal. The following table shows how the available $25$ marks are distributed: | Marks Awarded | Bounds on $N$ | Bounds on $M$ | Additional Constraints | | :---: | :---: | :---: | :---: | | 2 marks | $N = 2$ | $1 \leq M \leq 10^4$ | None | | 2 marks | $1 \leq N \leq 20$ | $1 \leq M \leq 10^4$ | None | | 4 marks | $1 \leq N \leq 1000$ | $1 \leq M \leq 10^4$ | None | | 6 marks | $1 \leq N \leq 1000$ | $1 \leq M \leq 10^8$ | None | | 2 marks | $1 \leq N \leq 500000$ | $1 \leq M \leq 10^8$ | All $m_i$ are equal. | | 3 marks | $1 \leq N \leq 500000$ | $1 \leq M \leq 10^8$ | At most 2 distinct $m_i$. | | 6 marks | $1 \leq N \leq 500000$ | $1 \leq M \leq 10^{12}$ | None |