Now Arkady's field has size h × w. He wants to enlarge it so that it is possible to place a rectangle of size a × b on it (along the width or along the length, with sides parallel to the field sides). Find the minimum number of extensions needed to reach Arkady's goal.

The first line contains five integers a, b, h, w and n (1 ≤ a, b, h, w, n ≤ 100 000) — the sizes of the rectangle needed to be placed, the initial sizes of the field and the number of available extensions.

The second line contains n integers a₁, a₂, ..., a_n (2 ≤ a_i ≤ 100 000), where a_i equals the integer a side multiplies by when the i-th extension is applied.

Print the minimum number of extensions needed to reach Arkady's goal. If it is not possible to place the rectangle on the field with all extensions, print -1. If the rectangle can be placed on the initial field, print 0.

In the first example it is enough to use any of the extensions available. For example, we can enlarge h in 5 times using the second extension. Then h becomes equal 10 and it is now possible to place the rectangle on the field.

 /**

  * Codeforces

  * Problem#799D

  * Accepted

  * Time: 31ms

  * Memory: 2500k

  */

 #include <bits/stdc++.h>

 using namespace std;

 typedef bool boolean;

 int a, b, c, d, n;

 int* arr;

 typedef class Data {

     public:

         int nc;

         int nd;

         int step;

         Data():nc(), nd(), step() {        }

         Data(long long nc, long long nd, int step):step(step) {

             this->nc = min(nc, (long long)a);

             this->nd = min(nd, (long long)b);

         }

         boolean isfin() {

             return nc >= a && nd >= b;

         }

         boolean operator < (Data b) const {

             if(nc != b.nc)    return nc < b.nc;

             return nd < b.nd;

         }

 }Data;

 inline void init() {

     scanf("%d%d%d%d%d", &a, &b, &c, &d, &n);

     arr = new int[(n + )];

     for(int i = ; i <= n; i++) {

         scanf("%d", arr + i);

     }

 }

 set<Data> se;

 queue<Data> que;

 inline int bfs(int c, int d) {

     Data s(c, d, );

     if(s.isfin())    return ;

     while(!que.empty())    que.pop();

     que.push(s);

     while(!que.empty()) {

         Data e = que.front();

         que.pop();

 //        printf("e:%d %d %d\n", e.nc, e.nd, e.step);

         if(e.nc < a) {

             Data eu(e.nc * 1LL * arr[e.step + ], e.nd, e.step + );

 //            printf("%d %d %d\n", eu.nc, eu.nd, eu.step);

             if(eu.isfin())    return eu.step;

             if(eu.step < n && !se.count(eu))

                 que.push(eu), se.insert(eu);

         }

         if(e.nd < b) {

             Data eu(e.nc, e.nd * 1LL * arr[e.step + ], e.step + );

 //            printf("%d %d %d\n", eu.nc, eu.nd, eu.step);

             if(eu.isfin())    return eu.step;

             if(eu.step < n && !se.count(eu))

                 que.push(eu), se.insert(eu);

         }

     }

     return -;

 }

 inline void solve() {

     sort(arr + , arr + n + , greater<int>());

     while(n && arr[n] == )    n--;

     int res1 = bfs(c, d), res2 = bfs(d, c);

     if(res1 == - && res2 == -)    puts("-1");

     else if(res1 == - || res2 == -)    printf("%d\n", max(res1, res2));

     else printf("%d\n", min(res1, res2));

 }

 int main() {

     init();

     solve();

     return ;

 }

Field expansion(bfs)

 /**

  * Codeforces

  * Problem#799D

  * Accepted

  * Time: 15ms

  * Memory: 2428k

  */

 #include <bits/stdc++.h>

 using namespace std;

 #define smin(a, b) a = min(a, b)

 typedef bool boolean;

 const signed int inf = 1e9;

 int a, b, c, d, n;

 int* arr;

 inline void init() {

     scanf("%d%d%d%d%d", &a, &b, &c, &d, &n);

     arr = new int[(n + )];

     for(int i = ; i <= n; i++) {

         scanf("%d", arr + i);

     }

 }

 int res = ;

 int deplimit = ;

 void dfs(int dep, int nc, int nd) {

 //    printf("%d %d %d\n", dep, nc, nd);

     if(nc >= a && nd >= b) {

         deplimit = dep, smin(res, dep);

 //        cout << dep << endl;

         return;

     }

     if(dep == n)    return;

     if(arr[dep + ] == ) {

         deplimit = dep;

         while(nc < a && dep < n)    nc <<= , dep++;

         while(nd < b && dep < n)    nd <<= , dep++;

         if(nc < a || nd < b)    return;

 //        cout << dep << endl;

         smin(res, dep);

     }

     if(dep == deplimit)    return;

     long long nnc = nc * 1LL * arr[dep + ], nnd = nd * 1LL * arr[dep + ];

     if(nc < a)    dfs(dep + , smin(nnc, (long long)a), nd);

     if(nd < b)    dfs(dep + , nc, smin(nnd, (long long)b));

 }

 inline void solve() {

     sort(arr + , arr + n + , greater<int>());

     while(n && arr[n] == )    n--;

     dfs(, c, d), dfs(, d, c);

     printf("%d\n", (res < ) ? (res) : (-));

 }

 int main() {

     init();

     solve();

     return ;

 }