题目描述

黑板上有一个整数 $n$，小云和小雀要将 $n$ 拆成若干个大于 $1$ 的整数，并进行一些操作。

每次操作有如下规则：一共有 $m$ 个数 $a_1,a_2,\cdots,a_m$ 可供选择。小云先手，小雀后手。每次，小云可以选择不超过 $x$ 个数，小雀可以选不超过 $y$ 个数。

设选出的数下标可重集合为 $S$，然后记 $p=\prod\limits_{i\in S}a_i$。小云可以让某个数 $\times p$，小雀可以让某个数 $\div p$（前提是 $p$ 能整除那个数）。

若要求小雀可以把每一个整数都变成 $1$。问最少需要把 $n$ 拆成几份。

输入格式

第一行四个整数 $n,m,x,y$。

第二行 $m$ 个整数 $a_1,a_2,\cdots,a_m$。

输出格式

输出一行一个整数，表示最少拆成几份才能满足要求。

如不能满足要求，输出 -1。

样例输入 #1

12 3 3 2
2 3 4

样例输出 #1

-1

样例输入 #2

18 2 2 3
7 1

样例输出 #2

2

样例输入 #3

12 3 2 3
7 8 11

样例输出 #3

-1

提示

下表表示数据最大值。

Subtask	$n$	$m$	$x,y$	$a_i$	特殊性质	分值
1	$10$	$2$		$10$	无	10
2	$5000$	$5$		$1000$	A	$10$
3					B	10
4					C	$10$
5					无	60

特殊性质 A：保证 $x\ge y$。

特殊性质 B：存在一个 $i$，使得 $n=a_i^p$，其中 $p$ 是正整数。

特殊性质 C：保证 $\sum\limits_{i=1}^{m} a_i=n$。

对于 $100\%$ 的数据，保证 $2\le a_i\leq n$。