Professional layer

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 ⋅ y seconds.

Print minimal time to enter to the professional layer or -1 if it's impossible.

Input

There are two numbers in the first line n and k (1 ≤ n ≤ 10^6, 1 ≤ k ≤ 10^{12}) — the number of judges and your skill in Cardbluff.

The second line contains n integers, where i-th number a_i (1 ≤ a_i ≤ 10^{12}) — the uncertainty of i-th judge

The third line contains n integers in the same format (1 ≤ e_i ≤ 10^9), e_i — the experience of i-th judge.

Output

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

Examples

Input

3 6 30 30 30 100 4 5

Output

18

Input

1 1000000 1 100

Output

0

Input

3 5 7 7 7 1 1 1

Output

-1

inputFormat

Input

There are two numbers in the first line n and k (1 ≤ n ≤ 10^6, 1 ≤ k ≤ 10^{12}) — the number of judges and your skill in Cardbluff.

The second line contains n integers, where i-th number a_i (1 ≤ a_i ≤ 10^{12}) — the uncertainty of i-th judge

The third line contains n integers in the same format (1 ≤ e_i ≤ 10^9), e_i — the experience of i-th judge.

outputFormat

Output

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

Examples

Input

3 6 30 30 30 100 4 5

Output

18

Input

1 1000000 1 100

Output

0

Input

3 5 7 7 7 1 1 1

Output

-1

样例

1 1000000
1
100

0

</p>