P12966 [CCO 2025] Asteroid Mining

现在是 2017 年，**Ryan** 是一名小行星矿工。他以开采小行星并在 **CCO**（天体货运前哨站）出售矿物为生。 在最近的一次采矿探险中，他开采了 $N$ 块矿物，其中第 $i$ 块矿物的价值为 $v_i$，质量为 $m_i$。**Ryan** 计划用他的火箭将一组矿物运送到 **CCO**，但他只剩下足够进行一次飞行的燃料。他计算出火箭能够安全携带的最大总质量为 $M$。由于 **Ryan** 的采矿技术，这些矿物具有一个特殊性质：对于任意两块矿物，其中一块的质量可以被另一块的质量整除。 帮助 **Ryan** 在火箭的限制下找到他能运送到 **CCO** 的最大总价值。

第一行包含两个以空格分隔的整数 $N$（$1 \leq N \leq 500000$）和 $M$（$1 \leq M \leq 10^{12}$）。 接下来的 $N$ 行，每行包含两个以空格分隔的整数 $v_i$（$1 \leq v_i \leq 10^{12}$）和 $m_i$（$1 \leq m_i \leq 10^{12}$），分别表示第 $i$ 块矿物的价值和质量。**此外，对于任意两块矿物 $i, j$（$1 \leq i, j \leq N$），要么 $m_i \mid m_j$，要么 $m_j \mid m_i$，其中 $a \mid b$ 表示 $a$ 是 $b$ 的因数（即 $\frac{b}{a}$ 是整数）。**

输出一行，包含一个整数，表示 **Ryan** 能运送到 **CCO** 的最大总价值。

**样例解释** **Ryan** 可以携带除第二块和第五块之外的所有矿物，以获得总价值 $1 + 200 + 9 + 100 = 310$。注意，这些矿物的总质量为 $1 + 6 + 2 + 1 = 10$。可以证明这是最优解。 以下表格展示了 25 分的分布情况： | 分值 | $N$ 的范围 | $M$ 的范围 | 额外约束 | | :---: | :---: | :---: | :---: | | 2 分 | $N = 2$ | $1 \leq M \leq 10^4$ | 无 | | 2 分 | $1 \leq N \leq 20$ | $1 \leq M \leq 10^4$ | 无 | | 4 分 | $1 \leq N \leq 1000$ | $1 \leq M \leq 10^4$ | 无 | | 6 分 | $1 \leq N \leq 1000$ | $1 \leq M \leq 10^8$ | 无 | | 2 分 | $1 \leq N \leq 500000$ | $1 \leq M \leq 10^8$ | 所有 $m_i$ 相等。 | | 3 分 | $1 \leq N \leq 500000$ | $1 \leq M \leq 10^8$ | 最多 2 种不同的 $m_i$。 | | 6 分 | $1 \leq N \leq 500000$ | $1 \leq M \leq 10^{12}$ | 无 | 翻译由 DeepSeek V3 完成