Professional layer

题意翻译

给定 $1 \le n \le 10^6$ 个正整数 $a_i,1 \le a_i≤10^{12}$ ，修改第 $i$ 个正整数 $a_i$ 的花费为$e_i,1 \le e_i \le 10^9$ ，以及正整数 $1 \le k \le 10^{12}$ 。 要求选出若干个正整数进行一次修改，使得修改后所有正整数的最大公约数等于 $1$ 。修改操作为：对于正整数 $a$ ，选择 $a$ 的一个约数 $d \le k$ ，把 $a$ 修改为$ \frac{a}{d}$ 。 设选出并修改的正整数有 $x$ 个，他们的花费之和为 $y$ ，则总的修改花费为 $x \times y$ 。求最小花费。

题目描述

Cardbluff is popular sport game in Telegram. Each Cardbluff player has ever dreamed about entrance in the professional layer. There are $ n $ judges now in the layer and you are trying to pass the entrance exam. You have a number $ k $ — your skill in Cardbluff. Each judge has a number $ a_i $ — an indicator of uncertainty about your entrance to the professional layer and a number $ e_i $ — an experience playing Cardbluff. To pass the exam you need to convince all judges by playing with them. You can play only one game with each judge. As a result of a particular game, you can divide the uncertainty of $ i $ -th judge by any natural divisor of $ a_i $ which is at most $ k $ . If GCD of all indicators is equal to $ 1 $ , you will enter to the professional layer and become a judge. Also, you want to minimize the total amount of spent time. So, if you play with $ x $ judges with total experience $ y $ you will spend $ x \cdot y $ seconds. Print minimal time to enter to the professional layer or $ -1 $ if it's impossible.

输入输出格式

输入格式

There are two numbers in the first line $ n $ and $ k $ ( $ 1 \leq n \leq 10^6 $ , $ 1 \leq k \leq 10^{12} $ ) — the number of judges and your skill in Cardbluff. The second line contains $ n $ integers, where $ i $ -th number $ a_i $ ( $ 1 \leq a_i \leq 10^{12} $ ) — the uncertainty of $ i $ -th judge The third line contains $ n $ integers in the same format ( $ 1 \leq e_i \leq 10^9 $ ), $ e_i $ — the experience of $ i $ -th judge.

输出格式

Print the single integer — minimal number of seconds to pass exam, or $ -1 $ if it's impossible

输入输出样例

输入样例 #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

题意翻译

给定 $1 \le n \le 10^6$ 个正整数 $a_i,1 \le a_i≤10^{12}$ ，修改第 $i$ 个正整数 $a_i$ 的花费为$e_i,1 \le e_i \le 10^9$ ，以及正整数 $1 \le k \le 10^{12}$ 。 要求选出若干个正整数进行一次修改，使得修改后所有正整数的最大公约数等于 $1$ 。修改操作为：对于正整数 $a$ ，选择 $a$ 的一个约数 $d \le k$ ，把 $a$ 修改为$ \frac{a}{d}$ 。 设选出并修改的正整数有 $x$ 个，他们的花费之和为 $y$ ，则总的修改花费为 $x \times y$ 。求最小花费。