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