在阿尔卡迪喜欢的一款游戏中,游戏过程发生在一个矩形场地上。在游戏过程中,阿尔卡迪可以为他的场地购买扩展,每个扩展都会将其中一个场地的大小扩大一定的次数。形式上,有 n 个扩展,其中第 i 个扩展将宽度或长度(由 Arkady 的选择)乘以 ai。每个扩展不能多次使用,扩展可以按任何顺序使用。
现在 Arkady 的场大小为 h × w。他想将其放大,以便可以在其上放置一个大小为 a × b 的矩形(沿宽度或沿长度,边与场边平行)。求出达到 Arkady 目标所需的最少扩展数量。
输入
第一行包含五个整数 a、b、h、w 和 n(1 ≤ a、b、h、w、n ≤ 100 000)——需要放置的矩形的大小、字段的初始大小和可用扩展的数量。
第二行包含 n 个整数 a1, a2, ..., an (2 ≤ ai ≤ 100 000),其中 ai 等于应用第 i 个扩展时 a 边乘以的整数。
输出
打印达到 Arkady 目标所需的最少扩展数。如果无法将矩形放置在具有所有扩展名的字段上,请打印 -1。如果矩形可以放置在初始字段上,则打印 0。
示例
输入 #1
3 3 2 4 4 2 5 4 10
输出 #1
1
输入 #2
3 3 3 3 5 2 3 5 4 2
输出 #2
0
输入 #3
5 5 1 2 3 2 2 3
输出 #3
-1
输入#4
3 4 1 1 3 2 3 2
输出#4
3
注意
在第一个示例中,使用任何可用的扩展就足够了。例如,我们可以使用第二个扩展将 h 放大 5 倍。然后 h 变为等于 10,现在可以将矩形放置在场地上。