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 JAVA):

Solution:
import java.util.*;
import java.io.*;

public class tr0 {
	static PrintWriter out;
	static StringBuilder sb;
	static final double EPS = 1e-9;
	static long mod = 1000000007;
	static int inf = (int) 1e9 + 2;
	static long[] fac;
	static Long[] a;
	static int[] si;
	static ArrayList<Integer> primes;
	static ArrayList<Integer>[] ad;
	static ArrayList<pair>[] d;
	static edge[] ed;
	static int[][] vis;
	static int[] l, ch;
	static int[] occ, p;
	static Queue<Integer>[] can;
	static String s;
	static long[][][] memo;
	static int n, m, k;
	static qu[] ar;
	static long[] sz;
	static long ans = 0;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		out = new PrintWriter(System.out);
		long a=sc.nextLong();
		long b=sc.nextLong();
		long x=sc.nextLong();
		long y=sc.nextLong();
		long d=gcd(x, y);
		x=x/d;
		y=y/d;
		out.print(Math.min(a/x,b/y));
		out.flush();
	}

	static void reroot(int u, int p, long vas) {
		long ll = vas;
		long v1=sz[u];
		long v2= p==-1 ? 0 : sz[p];
		if (p != -1) {
			ll-=sz[u];
			ll-=sz[p];
			long t=sz[u];
			sz[u]=sz[p];
			sz[p]=sz[p]-t;
			ll+=sz[u];
			ll+=sz[p];
	//		System.out.println(ll+" "+u+" "+Arrays.toString(sz));
			ans = Math.max(ans, ll);
		}
		for (int j : ad[u])
			if(j!=p)
			    reroot(j, u, ll);
            sz[u]=v1;
            if(p!=-1)
            	sz[p]=v2;
	}

	static void dfs(int u, int p) {
		sz[u] = 1;
	//	System.out.println(u+" "+p);
		for (int v : ad[u])
			if (v != p) {
				dfs(v, u);
				sz[u] += sz[v];
			}
		ans += sz[u];
	}

	static class qu implements Comparable<qu> {
		long a, b, c;

		qu(long i, long v, long x) {
			a = i;
			b = v;
			c = x;
		}

		public String toString() {
			return a + " " + b + " " + c;
		}

		public int compareTo(qu o) {
			if (Math.abs(o.a - o.b) <= Math.abs(a - b) && Math.abs(o.a - o.b) <= Math.abs(a - c))
				return 1;
			if (Math.abs(o.a - o.c) <= Math.abs(a - b) && Math.abs(o.a - o.c) <= Math.abs(a - c))
				return 1;
			else
				return -1;
		}
	}

	static class seg implements Comparable<seg> {
		int a;
		int b;
		int l;
		int r;
		int bit;

		seg(int s, int e, int x, int y, int bi) {
			a = s;
			b = e;
			l = x;
			r = y;
			bit = bi;
		}

		public String toString() {
			return a + " " + b + " " + l + " " + r + " " + bit;
		}

		public int compareTo(seg o) {
			// if(a==o.a)
			return bit - o.bit;
			// return
		}
	}

	static class pair {
		int to;
		int number;

		pair(int t, int n) {
			number = n;
			to = t;
		}

		public String toString() {
			return to + " " + number;
		}
	}

	static long modPow(long a, int e)

	{
		long res = 1;
		while (e > 0) {
			if ((e & 1) == 1)
				res = (res * a) % mod;
			a = (a * a) % mod;
			e >>= 1;
		}
		return res;
	}

	static long inver(long x) {
		long a = x;
		long e = (mod - 2);
		long res = 1;
		while (e > 0) {
			if ((e & 1) == 1) {
				res = ((1l * res * a) % mod);
			}
			a = ((1l * a * a) % mod);
			e >>= 1;
		}
		return res % mod;
	}

	static class edge implements Comparable<edge> {
		int from;
		int to;
		int number;

		edge(int f, int t, int n) {
			from = f;
			to = t;
			number = n;
		}

		public String toString() {
			return from + " " + to + " " + number;
		}

		public int compareTo(edge f) {
			return f.number - number;
		}
	}

	static void seive(int N) {
		si = new int[N];
		primes = new ArrayList<>();
		si[1] = 1;
		for (int i = 2; i < N; i++) {
			if (si[i] == 0) {
				si[i] = i;
				primes.add(i);
			}
			for (int j = 0; j < primes.size() && primes.get(j) <= si[i] && (i * primes.get(j)) < N; j++)
				si[primes.get(j) * i] = primes.get(j);

		}
	}

	static long fac(int n) {
		if (n == 0)
			return fac[n] = 1;
		if (n == 1)
			return fac[n] = 1;
		long ans = 1;
		for (int i = 1; i <= n; i++)
			fac[i] = ans = (i % mod * ans % mod) % mod;
		return ans % mod;
	}

	static long gcd(long a, long b) {

		if (b == 0)
			return a;
		return gcd(b, a % b);
	}

	static class unionfind {
		int[] p;
		int[] size;
		int[] max;
		int num;

		unionfind(int n) {
			p = new int[n];
			size = new int[n];
			max = new int[n];
			for (int i = 0; i < n; i++) {
				p[i] = i;
				max[i] = i;
			}
			Arrays.fill(size, 1);
			num = n;
		}

		int findSet(int v) {
			if (v == p[v])
				return v;

			max[v] = Math.max(max[v], max[p[v]]);

			p[v] = findSet(p[v]);

			max[v] = Math.max(max[v], max[p[v]]);

			return p[v];
		}

		boolean sameSet(int a, int b) {
			a = findSet(a);
			b = findSet(b);
			if (a == b)
				return true;
			return false;
		}

		int max() {
			int max = 0;
			for (int i = 0; i < size.length; i++)
				if (size[i] > max)
					max = size[i];
			return max;
		}

		boolean combine(int a, int b) {
			a = findSet(a);
			b = findSet(b);
			if (a == b)
				return true;
			// System.out.println(num+" ppp");
			num--;
			if (size[a] > size[b]) {
				p[b] = a;
				max[a] = Math.max(max[a], max[b]);
				size[a] += size[b];

			} else {
				p[a] = b;
				max[b] = Math.max(max[a], max[b]);
				size[b] += size[a];
			}
			return false;
		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}