Cardbluff 是 Telegram 中流行的体育游戏。每个 Cardbluff 玩家都曾梦想进入职业级别。该层现在有$$$n$$$ 评委,你正在努力通过入学考试。你有一个数字$$$k$$$——你的卡牌布拉夫技能。
每个裁判都有一个数字 $$$a_i$$$ — 表示您进入职业级别的不确定性指标,还有一个数字 $$$e_i$$$ — 玩 Cardbluff 的体验。要通过考试,您需要通过与所有评委一起玩来说服他们。每位裁判只能玩一场游戏。作为特定游戏的结果,您可以将第 $$$i$$$ 个法官的不确定性除以 $$$a_i$$$ 的任何自然除数,最多为 $$$k$$$。如果所有指标的GCD等于$$$1$$$,则您将进入专业层并成为评委。
此外,您希望最大限度地减少所花费的时间总量。因此,如果您与具有总经验 $$$y$$$ 的 $$$x$$$ 裁判一起比赛,您将花费 $$$x \cdot y$$$ 秒。
打印进入专业层的最短时间,如果不可能,则打印$$$-1$$$。
输入
第一行有两个数字 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^6$$$, $$$1 \leq k \leq 10^{12}$$$) — 法官的数量和你在 Cardbluff 中的技能。
第二行包含 $$$n$$$ 整数,其中 $$$i$$$-第 $$$a_i$$$ ($$$1 \leq a_i \leq 10^{12}$$$) — 第 $$$i$$$ 个判断的不确定性
第三行包含相同格式的 $$$n$$$ 整数 ($$$1 \leq e_i \leq 10^9$$$),$$$e_i$$$ — 第 $$$i$$$ 个法官的经验。
输出
打印单个整数 - 通过考试的最小秒数,如果不可能,则打印 $$$-1$$$
示例
输入 #1
3 6 30 30 30 100 4 5
输出 #1
18
输入 #2
1 1000000 1 100
输出 #2
0
输入 #3
3 5 7 7 7 1 1 1
输出 #3
-1