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.io.BufferedWriter;
	import java.io.IOException;
	import java.io.InputStream;
	import java.io.OutputStream;
	import java.io.OutputStreamWriter;
	import java.io.PrintWriter;
	import java.io.Writer;
	import java.util.Arrays;
	import java.util.InputMismatchException;
	import java.util.*;
	import java.io.*;
	import java.math.*;
	public class Main
	{
	   public static long pow(long a, long b)
		{
			long result=1;
			while(b>0)
			{
				if (b % 2 != 0)
				{
					result=(result*a);
					b--;
				} 
				a=(a*a);
				b /= 2;
			}   
					return result;
		}
		public static long fact(long num)
		{
					long fact=1;
					int i=0;
					for(i=1; i<=num; i++)
					{
						fact=fact*i;
					}
					return fact;
				}
				public static long gcd(long a, long b)
				{
					if (a == 0)
						return b;
					return gcd(b%a, a);
				}
				
				public static long lcm(int a,int b)
				{
					return a * (b / gcd(a, b));
				}
				public static long sum(int h)
				{
					return (h*(h+1)/2);
				}
				public static void dfs(int parent,boolean[] visited)
				{
					ArrayList<Integer> arr=new ArrayList<Integer>();
					arr=graph.get(parent);
					visited[parent]=true;
					for(int i=0;i<arr.size();i++)
					{
						int num=arr.get(i);
						if(visited[num]==false)
						{
							dfs(num,visited);
						}
						else
						{
							
						}
					}
				}
				static int[] storing1;
				static int[] storing2;
				static ArrayList<ArrayList<Integer>> graph;
				static InputReader in=new InputReader(System.in);
				static OutputWriter out=new OutputWriter(System.out);
				public static long Long()
				{
					String s=in.String();
					return Long.parseLong(s);
				}
				public static void pln(String value)
				{
					System.out.println(value);
				}
				public static void main(String args[])throws IOException
				{
				//	long a=pow(26,1000000005);
				 //   BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
					ArrayList<Integer> index=new ArrayList<>();
					ArrayList<Integer> index1=new ArrayList<>();
					ArrayList<Character> ar2=new ArrayList<>();
					TreeSet<Integer> ts=new TreeSet<>();
					TreeSet<Integer> ts1=new TreeSet<>();
					HashMap<Integer,Integer> hash=new HashMap<Integer,Integer>();
					HashMap<Integer,Integer> hash1=new HashMap<Integer,Integer>();
					long a=Long();
					long b=Long();
					long x=Long();
					long y=Long();
					long g=gcd(x,y);
					x=x/g;
					y=y/g;
					long ans=a/x;
					long ans1=b/y;
					pln(Math.min(ans,ans1)+"");
				}
				
			}
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			class InputReader {
				 
				private InputStream stream;
				private byte[] buf = new byte[1024];
				private int curChar;
				private int numChars;
				private SpaceCharFilter filter;
			 
				public InputReader(InputStream stream) {
					this.stream = stream;
				}
			 
				public int read() {
					if (numChars== -1)
						throw new InputMismatchException();
					if (curChar >= numChars) {
						curChar = 0;
						try {
							numChars = stream.read(buf);
						} catch (IOException e) {
							throw new InputMismatchException();
						}
						if (numChars <= 0)
							return -1;
					}
					return buf[curChar++];
				}
				public int Int() {
					int c = read();
					while (isSpaceChar(c))
						c = read();
					int sgn = 1;
					if (c == '-') {
						sgn = -1;
						c = read();
					}
					int res = 0;
					do {
						if (c < '0' || c > '9')
							throw new InputMismatchException();
						res *= 10;
						res += c - '0';
						c = read();
					} while (!isSpaceChar(c));
					return res * sgn;
				}
			 
				public String String() {
					int c = read();
					while (isSpaceChar(c))
						c = read();
					StringBuilder res = new StringBuilder();
					do {
						res.appendCodePoint(c);
						c = read();
					} while (!isSpaceChar(c));
					return res.toString();
				}
			 
				public boolean isSpaceChar(int c) {
					if (filter != null)
						return filter.isSpaceChar(c);
					return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
				}
			 
				public String next() {
					return String();
				}
			 
				public interface SpaceCharFilter {
					public boolean isSpaceChar(int ch);
				}
			}
			 
			class OutputWriter {
				private final PrintWriter writer;
			 
				public OutputWriter(OutputStream outputStream) {
					writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
				}
			 
				public OutputWriter(Writer writer) {
					this.writer = new PrintWriter(writer);
				}
			 
				public void print(Object...objects) {
					for (int i = 0; i < objects.length; i++) {
						if (i != 0)
							writer.print(' ');
						writer.print(objects[i]);
					}
				}
			 
				public void printLine(Object...objects) {
					print(objects);
					writer.println();
				}
			 
				public void close() {
					writer.close();
				}
			 
				public void flush() {
					writer.flush();
				}
			 
				}
			 
				class IOUtils {
			 
				public static int[] readIntArray(InputReader in, int size) {
					int[] array = new int[size];
					for (int i = 0; i < size; i++)
						array[i] = in.Int();
					return array;
				}
			 
				}