Одна из игр, которыми увлекается Аркадий, происходит на прямоугольном участке. В процессе игры Аркадий может покупать расширения для своего участка, каждое расширение в несколько раз увеличивает любую из двух сторон его участка. Формально, есть n расширений, i-е из них позволяет увеличить длину или ширину (по выбору Аркадия) участка в ai раз. Каждое расширение можно использовать не более одного раза, расширения можно использовать в любом порядке.
Сейчас участок Аркадия имеет размер h × w. Он хочет его расширить так, чтобы возможно было разместить на участке прямоугольное поле размером a × b (вдоль или поперек, параллельно сторонам участка). Найдите минимальное число расширений, которое будет достаточно Аркадию для достижения своей цели.
В первой строке следуют пять целых чисел a, b, h, w и n (1 ≤ a, b, h, w, n ≤ 100 000) — размеры поля, которое нужно разместить на участке, размеры участка, а также количество доступных расширений.
Во второй строке следует последовательность n целых чисел a1, a2, ..., an (2 ≤ ai ≤ 100 000), где ai равно количеству раз, в которое может быть увеличена сторона при применении к ней i-го расширений.
Выведите минимальное число расширений, которое будет достаточно Аркадию для достижения своей цели. Если невозможно поместить поле на участок после использования всех расширений, выведите -1. Если поле изначально помещается на участок, выведите 0.
3 3 2 4 4
2 5 4 10
1
3 3 3 3 5
2 3 5 4 2
0
5 5 1 2 3
2 2 3
-1
3 4 1 1 3
2 3 2
3
В первом примере достаточно использовать любое из доступных расширений. Например, можно увеличить h в 5 раз, использовав второе расширение. Тогда h станет равно 10 и станет возможно поместить поле на получившийся расширенный участок.
Название |
---|