题目描述

现在有 $K$种浓度的糖浆，浓度分别为 $$\frac{a_1}{M}, \frac{a_2}{M},\cdots,\frac{a_k}{M}$$

这$K$种原料的数量是无限的。

每次可以将整数毫升的几种糖浆勾兑到一起，就可以得到新的浓度的糖浆。

问：想要得到浓度为 $N/M$ 的糖浆 ，至少要用多少毫升的糖浆原料。

如果得不到，输出 $-1$ 。

输入格式

第一行输入 $3$ 个整数 $K, N, M$。

第二行，$k$ 个整数 $a_i$。

输出格式

输出一行一个整数，表示答案。

样例

输入

4 40 100
10 30 45 50

输出

2

数据范围

对于 $20\%$ 的数据 $M\le 8$。

对于额外 $10\%$ 的数据 $K=2$。

对于额外 $20\%$ 的数据 $K=3$ 。

对于 $100\%$ 的数据 $N\le M \le 1 000$ ，$K\le 1 000 00$,$a_i\le M$。

• 时间限制：1S

• 空间限制：512MB