Miss Sloane

Time limit5sMemory limit1024 MB

Summary

Choose senators to lobby, dividing each chosen a_i by a divisor at most k, so that the gcd of all final values is greater than 1, minimizing the total lobbying time.

Level: Hard8 of 10
Topics: Number theory, Greedy, Sorting
Solved: No attempts yet

Miss Sloane

In the movie, Elizabeth Sloane, a ruthless lobbyist, and her firm are approached by Bill Sanford, a gun manufacturing representative who leads the opposition to the Heaton-Harris bill. The bill would expand background checks on gun purchases. Sanford proposes to target female voters to overturn their maternal tendencies when they vote. Sloane mocked this idea. She believed that the power of congressmen should be used for the benefit of everyone rather than the congressmen themselves, and that this is the right thing to do.

In this problem you play the other side. Sloane takes Sanford's role in the campaign against the Heaton-Harris bill. Your goal is to lobby the senators so that they cannot reach an agreement on the bill. There are $n$ senators in Congress. Each senator $i$ has a positive integer $a_i$ that represents his or her general opinions on various public issues. The resistance of each senator to lobbying is a positive integer $e_i$ . If the greatest common divisor of the public-issue indicators is not 1, the senators reach an agreement and the bill passes. Your goal is to prevent this.

Sloane's lobbying ability is an integer $k$ . The campaign proceeds as follows. In each round, Sloane may approach one senator, for example the $i$ th senator, and influence his or her opinions on public issues of her choice. As a result, she can divide $a_i$ by a natural divisor that is no larger than $k$ . The senators are wary, so Sloane can influence each senator at most once. Also, as more senators are lobbied, each further lobbying takes longer. Suppose Sloane has already lobbied $x$ senators whose total resistance is $y$ . If she lobbies the $i$ th senator next, that lobbying takes $y + e_i (x + 1)$ units of time.

Find the minimum total time needed to complete the campaign. If it is impossible, print -1.

Input

The first line contains two integers $n$ and $k$ , the number of senators and Sloane's lobbying ability. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ , the indicators of the senators. The third line contains $n$ integers $e_1, e_2, \ldots, e_n$ , the resistances of the senators.

Output

Print the minimum total time needed to complete the campaign, or -1 if it is impossible.

Constraints

$1 \le n \le 10^6$

$1 \le k \le 10^{12}$

$1 \le a_i \le 10^{12}$

$1 \le e_i \le 10^9$

Examples3

Example 1
Input
```
3 6
30 30 30
100 4 5
```
Expected output
```
18
```
Example 2
Input
```
1 1000000
1
100
```
Expected output
```
0
```
Example 3
Input
```
3 5
7 7 7
1 1 1
```
Expected output
```
-1
```