题目描述

lbw 是一名小行星矿工。

在最近的一次采矿探险中，他开采了 $N$ 块矿物，其中第 $i$ 块矿物的价值为 $v_i$，质量为 $m_i$。lbw 计划用他的火箭将一组矿物运送到基地，但他只剩下足够进行一次飞行的燃料。他计算出火箭能够安全携带的最大总质量为 $M$。由于 lbw 的采矿技术，这些矿物具有一个特殊性质：对于任意两块矿物，其中一块的质量可以被另一块的质量整除。

帮助 lbw 在火箭的限制下找到他能运送的最大总价值。

输入格式

第一行包含两个以空格分隔的整数 $N$和 $M$。

接下来的 $N$ 行，每行包含两个以空格分隔的整数 $v_i$和 $m_i$，分别表示第 $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}$ 是整数）。

输出格式

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

输入样例

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

输出样例

310

说明提示

样例解释

lbw 可以携带除第二块和第五块之外的所有矿物，以获得总价值 $1 + 200 + 9 + 100 = 310$。注意，这些矿物的总质量为 $1 + 6 + 2 + 1 = 10$。可以证明这是最优解。

以下表格展示了 100 分的分布情况：

输入样例 #2

1 382233057012
803921582021 4

输出样例 #2

803921582021

输入样例 #3

2 98396626495
366938466589 16
679748728634 16

输出样例 #3

1046687195223

数据范围

（$1 \leq N \leq 500000$）

（$1 \leq M \leq 10^{12}$）

（$1 \leq v_i \leq 10^{12}$）

（$1 \leq m_i \leq 10^{12}$）