← 返回题目列表

Codeforces · 799/D

D. 领域扩展

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

在阿尔卡迪喜欢的一款游戏中,游戏过程发生在一个矩形场地上。在游戏过程中,阿尔卡迪可以为他的场地购买扩展,每个扩展都会将其中一个场地的大小扩大一定的次数。形式上,有 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,现在可以将矩形放置在场地上。