题目描述

译自 CCO 2025 Day1 T1「Asteroid Mining」。

故事发生在 $2217$ 年，Ryan 是一名小行星矿工。他以挖掘小行星并将其出售给 CCO（Celestial Cargo Outpost）为生。

在最近的一次挖掘探险中，他开采了 $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$ 的因数（即 $b / a$ 为整数）。

输出格式

在一行中输出一个整数，表示 Ryan 能够运送到 CCO 的最大总价值。

样例

输入：

6 10
1 1
5 2
200 6
9 2
6 2
100 1

输出：

310

Ryan 可以选择除第 $2$ 块和第 $5$ 块以外的所有矿物碎片，从而获得总价值 $1+200+9+100=310$。注意，所选矿物碎片的总质量为 $1+6+2+1=10$。可以证明这是最优解。

数据范围与提示

详细子任务附加限制及分值如下表所示。