← 返回题目列表

Codeforces · 73/E

E. 明日视窗

中文机器翻译题面 查看原题

Vasya 玩《上古巨魔 III:Morrowindows》。他的库存中有很多物品,但是物品的大小没有限制。 Vasya 不知道物品总数,但他确定库存中的物品不超过 x 且不少于 2 件。游戏的新补丁似乎可以以 n 种不同的模式查看库存。在模式 i 下显示的是页面上所有库存项目的分区,其中每个项目(可能除了最后一个)都准确显示 ai 项目。此外,每种模式还显示完整列表中有多少页bi。伟大的!也许这些信息足以让瓦西亚找到所需的号码。而且,非常有趣的是,Vasya可以看到库存来确定其中物品数量的最少模式是多少?

Vasya 无法使用在某种模式下查看库存时收到的信息来选择下一步操作。 IE。 Vasya 首先选择一组模式,然后查看所有结果并确定大小。

知道 ai, x 的数字并假设 Vasya 非常聪明,检查他是否可以唯一确定其库存中的物品数量,以及如果他知道数字 ai, x 并且在模式 i 中查看物品后他能够知道数字 bi,则需要多少种模式才能做到这一点。

输入

第一行包含两个整数 n 和 x (0 ≤ n ≤ 105, 2 ≤ x ≤ 109)。第二行包含整数 ai (1 ≤ ai ≤ 109)。所有ai中的一些数字可能是相等的。

输出

输出唯一确定库存中物品数量所需的最少模式。如果没有解输出 - 1。

示例

输入 #1

2 4
2 3

输出 #1

2

输入 #2

1 4
2

输出 #2

-1

注意

在第二个示例中,Vasya 无法唯一确定项目计数,因为可以在两个页面上显示 3 个项目以及 4 个项目。