4557. World Line

单点时限: 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 奖励。

创建: 2 年,10 月前.

修改: 2 年,10 月前.

最后提交: 1 年,11 月前.

来源: N/A

题目标签