**7 人解决**，16 人已尝试。

**8 份提交通过**，共有 172 份提交。

**7.9** EMB 奖励。

**单点时限: **1.5 sec

**内存限制: **256 MB

It is all choosen by Steins Gate!

As a fan of Steins Gate, you made a game with its background. The whole game world is composed of all positive integers. In the game, $1$ represents the public event, prime numbers represent events that affect the world line, and composite numbers represent world lines.

When a prime number $p$ is a factor of the composite number $c$, it means that the event $p$ can affect the world line $c$. If all events affecting a world line occur, you can choose to reach the world line. For example, reaching world line 12 requires events 2 and 3 to occur. Of course, if events 2 and 3 happen, you can reach an infinite number of world lines such as $4,6,8,9,12…$

As a game developer, you know there are $n$ world lines $a_ 1,…,a_n$ you really want to reach. Because of your excellent performance in developing the game, you get the reward opportunity of $len$: you can choose $1$ or any event as the base point $p$, and all events in the closed interval $[p + 1, p + len] $ will happen.

You want to reach all $n$ world lines, and if there are multiple choices, always give priority to the one with a larger base point. If all $n$ world lines can be reached, you should find the largest base point $p$, and you should output the total number of events that will happen (in other words, output the number of primes in $[p+1,p+len]$). Otherwise, just output $-1$ .

The first line contains two positive integers $n、len$，represent the number of world lines and the size of reward, respectively.

The second line contains $n $ positive integers, $a_1,…,a_n $ represents the world line.

An integer $ans$，represents the answer.

Input

2 11 33 35

Output

5

Input

1 10 39

Output

-1

$1\leq n\leq 200$

$1\leq len \leq 4*10^5$

$1< a_i\leq 10^{18}$，$a_i$ are composite numbers

**Sample Explanation:**

For input1, choose 2 as the base point, all events in [3, 13] will happen, they are 3,5,7,11,13.

For input2, there is no choice.

**7 人解决**，16 人已尝试。

**8 份提交通过**，共有 172 份提交。

**7.9** EMB 奖励。

**创建**: 1 年，11 月前.

**修改**: 1 年，11 月前.

**最后提交**: 1 年前.

**来源**: N/A

题目标签