Problem: Monocarp has decided to buy a new TV set and hang it on the wall in his flat. The wall has enough free space so Monocarp can buy a TV set with screen width not greater than a and screen height not greater than b. Monocarp is also used to TV sets with a certain aspect ratio: formally, if the width of the screen is w, and the height of the screen is h, then the following condition should be met: w/h = x/y.

There are many different TV sets in the shop. Monocarp is sure that for any pair of positive integers w and h there is a TV set with screen width w and height h in the shop.

Monocarp isn't ready to choose the exact TV set he is going to buy. Firstly he wants to determine the optimal screen resolution. He has decided to try all possible variants of screen size. But he must count the number of pairs of positive integers w and h, beforehand, such that (w ≤ a), (h ≤ b) and (w/h = x/y).

In other words, Monocarp wants to determine the number of TV sets having aspect ratio x/y, screen width not exceeding a, and screen height not exceeding b. Two TV sets are considered different if they have different screen width or different screen height.

Input

The first line contains four integers a, b, x, y (1 ≤ a, b, x, y ≤ 10^{18}) — the constraints on the screen width and height, and on the aspect ratio.

Output

Print one integer — the number of different variants to choose TV screen width and screen height so that they meet the aforementioned constraints.

Examples

Input

17 15 5 3


Output

3


Input

14 16 7 22


Output

0


Input

4 2 6 4


Output

1


Input

1000000000000000000 1000000000000000000 999999866000004473 999999822000007597


Output

1000000063

Note

In the first example, there are 3 possible variants: (5, 3), (10, 6), (15, 9).

In the second example, there is no TV set meeting the constraints.

In the third example, there is only one variant: (3, 2).

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
void solve();
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  {
    solve();
    cout << "\n";
  }
  cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
  return 0;
}
long long ceils(long long x, long long y) { return x / y + ((x % y) != 0); }
long long mult(long long x, long long y, long long mod) {
  return (x * y) % mod;
}
long long bin_pow(long long x, long long p, long long mod) {
  if (p == 0) return 1;
  if (p & 1) return mult(bin_pow(x, p - 1, mod), x, mod);
  return bin_pow(mult(x, x, mod), p / 2, mod);
}
bool isPrime(long long n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
vector<bool> is_prime(1e6 + 1, true);
long long binomialCoeffSpaceEff(long long n, long long k) {
  long long C[k + 1];
  memset(C, 0, sizeof(C));
  C[0] = 1;
  for (long long i = 1; i <= n; i++) {
    for (long long j = min(i, k); j > 0; j--) C[j] = (C[j] + C[j - 1]) % MOD;
  }
  return C[k];
}
long long primeFactors(long long n) {
  vector<long long> ar;
  long long i = 2;
  while (n > 0) {
    if (i > n) break;
    if (n % i == 0) {
      ar.push_back(i);
      while (n > 0 and n % i == 0) n = n / i;
    }
    i++;
  }
  return ar.size();
}
vector<pair<long long, long long> > primeFactorsFreq(long long n) {
  vector<pair<long long, long long> > ar;
  long long i = 2;
  while (n > 0) {
    if (i > n) break;
    if (n % i == 0) {
      long long cnt = 0;
      while (n > 0 and n % i == 0) n = n / i, cnt++;
      ar.push_back(make_pair(i, cnt));
    }
    i++;
  }
  return ar;
}
void seive() {
  is_prime[0] = is_prime[1] = false;
  for (long long i = 2; i * i <= 1e6 + 1; i++) {
    if (is_prime[i]) {
      for (long long j = i * i; j <= 1e6 + 1; j += i) is_prime[j] = false;
    }
  }
}
bool isSorted(vector<long long> &ar) {
  long long n = ar.size();
  for (long long i = 0; i < n - 1; i++) {
    if (ar[i + 1] < ar[i]) return false;
  }
  return true;
}
long long fastPower(long long x, long long y) {
  long long res = 1;
  while (y > 0) {
    if (y & 1) res = (res * x) % MOD;
    y = y >> 1;
    x = (x * x) % MOD;
  }
  return res;
}
long long kadanesAlgo(vector<long long> ar) {
  long long n = ar.size();
  long long currMax = 0;
  long long mx = INT_MIN;
  for (long long i = 0; i < n; i++) {
    currMax += ar[i];
    if (currMax <= ar[i]) {
      currMax = ar[i];
    }
    mx = max(currMax, mx);
  }
  return mx;
}
pair<long long, long long> kadanesAlgoIdx(vector<long long> ar) {
  long long n = ar.size();
  long long currMax = 0;
  long long mx = INT_MIN;
  long long a = 0, b;
  for (long long i = 0; i < n; i++) {
    currMax += ar[i];
    if (currMax <= ar[i]) {
      currMax = ar[i];
      a = i;
    }
    if (mx < currMax) {
      mx = currMax;
      b = i;
    }
  }
  return make_pair(a, b);
}
long long gcd(long long a, long long b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long fac(long long n) {
  while (n % 4 == 0) {
    n /= 4;
  }
  for (long long i = 3; i <= sqrt(n); i += 2) {
    while (n % (i * i) == 0) {
      n /= (i * i);
    }
  }
  return n;
}
long long findLCS(string a, string b, long long m, long long n) {
  long long LCS[m + 1][n + 1];
  long long result = 0;
  for (long long i = 0; i <= m; i++) {
    for (long long j = 0; j <= n; j++) {
      if (i == 0 || j == 0)
        LCS[i][j] = 0;
      else if (a[i - 1] == b[j - 1]) {
        LCS[i][j] = LCS[i - 1][j - 1] + 1;
        result = max(result, LCS[i][j]);
      } else
        LCS[i][j] = 0;
    }
  }
  return result;
}
long long add(long long x, long long y) {
  x += y;
  if (x >= MOD) return x - MOD;
  return x;
}
long long sub(long long x, long long y) {
  x -= y;
  if (x < 0) return x + MOD;
  return x;
}
long long f(long long x) {
  long long d = 0;
  while (x > 0) {
    d += x % 10;
    x /= 10;
  }
  return d;
}
vector<string> generateGray(long long n) {
  if (n <= 0) return {"0"};
  if (n == 1) {
    return {"0", "1"};
  }
  vector<string> recAns = generateGray(n - 1);
  vector<string> mainAns;
  for (long long i = 0; i < recAns.size(); i++) {
    string s = recAns[i];
    mainAns.push_back("0" + s);
  }
  for (long long i = recAns.size() - 1; i >= 0; i--) {
    string s = recAns[i];
    mainAns.push_back("1" + s);
  }
  return mainAns;
}
void generateGraya(long long n) {
  vector<string> a;
  a = generateGray(n);
  for (long long i = 0; i < a.size(); i++) cout << a[i] << endl;
}
void move(long long disks, long long source, long long auxiliary,
          long long target) {
  if (disks > 0) {
    move(disks - 1, source, target, auxiliary);
    cout << source << "  " << target << endl;
    move(disks - 1, auxiliary, source, target);
  }
}
long double polyarea(long double n, long double a) {
  if (a < 0 && n < 0) return -1;
  long double A = (a * a * n) / (4 * tan((180 / n) * 3.14159 / 180));
  return A;
}
long long eqDiv(long long *a, long long s1, long long s, long long l) {
  if (l == 0) return abs((s - s1) - s1);
  return min(eqDiv(a, s1 + a[l], s, l - 1), eqDiv(a, s1, s, l - 1));
}
long long noofdigit(long long n) {
  long long x = 0;
  while (n > 0) {
    n /= 10;
    x++;
  }
  return x;
}
long long factorial(long long n) {
  if (n == 0) return 1;
  return (n * factorial(n - 1) % MOD) % MOD;
}
void solve() {
  long long a, b, x, y;
  cin >> a >> b >> x >> y;
  while (gcd(x, y) != 1) {
    long long t = gcd(x, y);
    x /= t;
    y /= t;
  }
  long long fin = min(a / x, b / y);
  cout << fin;
}