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: $\frac{w}{h} = \frac{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 \le a)$, $(h \le b)$ and $(\frac{w}{h} = \frac{x}{y})$.

In other words, Monocarp wants to determine the number of TV sets having aspect ratio $\frac{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 \le a, b, x, y \le 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)$.

Difficulty: interview

Starter code:

Solutions:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

a, b, x, y = list(map(int, input().split()))

g = gcd(x, y)
x //= g
y //= g


print(min(a // x, b // y))


from sys import stdin, stdout


def gcd(a, b):
    if not b:
        return a
    else:
        return gcd(b, a % b)


a, b, x, y = map(int, stdin.readline().split())
g = gcd(x, y)
x //= g
y //= g

l, r = 0, 10 ** 18 + 1
while r - l > 1:
    m = (l + r) >> 1
    
    if m * x <= a and m * y <= b:
        l = m
    else:
        r = m

stdout.write(str(l))

from math import gcd

a, b, x, y = map(int, input().split())
x, y = x // gcd(x, y), y // gcd(x, y)
print(min(a // x, b // y))

from fractions import gcd as g

(a, b, x, y) = list(map(int, input().split()))

k = g(x, y)

x //= k
y //= k

print(min(a // x, b // y))


USE_STDIO = False

if not USE_STDIO:
    try: import mypc
    except: pass

def gcd(x, y):
    if x % y == 0: return y
    return gcd(y, x % y)

def main():
    a, b, x, y = list(map(int, input().split(' ')))
    g = gcd(x, y)
    x, y = x // g, y // g
    ans = min(a // x, b // y)
    print(ans)

def __starting_point():
    main()




__starting_point()

a, b, x, y = list(map(int, input().split()))

from fractions import gcd

x, y = x // gcd(x, y), y // gcd(x, y)

print(min(a // x, b // y))


import math
import sys
a, b, x, y = list(map(int, input().split()))
g = math.gcd(x, y)
x //= g
y //= g
l = 0
r = 10**18
while r - l > 1:
    mid = (r + l) // 2
    if x * mid > a or y * mid > b:
        r = mid
    else:
        l = mid
if x * r > a or y * r > b:
    print(l)
else:
    print(r)


a,b,x,y = list(map(int,input().rsplit()))
def gdc(a,b):
	if b == 0:
		return a
	return gdc(b,a%b)

g = gdc(x,y)
x //= g
y //= g

print(min(a//x,b//y))

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


a, b, x, y = map(int, input().split())
k = gcd(x, y)
x //= k
y //= k
print(min(a // x, b // y))

def gcd(x, y):
    return x if y == 0 else gcd(y, x % y)

a,b,x,y = list(map(int,input().split()))


val  = gcd(x, y)
x //= val
y //= val

a_min = a // x
b_min = b // y

print(min(a_min, b_min))


from copy import deepcopy
import itertools
from bisect import bisect_left
from bisect import bisect_right
import math
from collections import deque
from collections import Counter


def read():
    return int(input())


def readmap():
    return map(int, input().split())


def readlist():
    return list(map(int, input().split()))


a, b, x, y = readmap()

g = math.gcd(x, y)

print(min(a // (x // g), b // (y // g)))

#JMD
#Nagendra Jha-4096

 
import sys
import math

#import fractions
#import numpy
 
###File Operations###
fileoperation=0
if(fileoperation):
    orig_stdout = sys.stdout
    orig_stdin = sys.stdin
    inputfile = open('W:/Competitive Programming/input.txt', 'r')
    outputfile = open('W:/Competitive Programming/output.txt', 'w')
    sys.stdin = inputfile
    sys.stdout = outputfile

###Defines...###
mod=1000000007
 
###FUF's...###
def nospace(l):
    ans=''.join(str(i) for i in l)
    return ans
 
 
 
##### Main ####
t=1
for tt in range(t):
    #a=list(map(int,sys.stdin.readline().split(' ')))
    a,b,x,y= map(int, sys.stdin.readline().split(' '))
    g=math.gcd(x,y)
    x=x//g
    y=y//g

    print(min(a//x,b//y))
    
#####File Operations#####
if(fileoperation):
    sys.stdout = orig_stdout
    sys.stdin = orig_stdin
    inputfile.close()
    outputfile.close()

def gcd(a, b):
	while b != 0:
		a %= b
		a, b = b, a
	return a

a, b, x, y = [int(i) for i in input().split()]

g = gcd(x, y)
x //= g
y //= g

print(min(a // x, b // y))

a, b, x, y = list(map(int, input().split()))
from math import gcd
g = gcd(x, y)
x //= g
y //= g
print(min(a // x, b // y))


#autogenerated (:'D)
read_numbers = lambda: list(map(int, input().split()))
INF = 1 << 64

#main
from fractions import gcd

a, b, x, y = read_numbers()
g = gcd(x, y)
x, y = x // g, y // g
print(min(a // x, b // y))

from fractions import gcd

def __starting_point():
    a, b, x, y = list(map(int, input().split()))
    c = gcd(x, y)
    x, y = x // c, y // c
    answer = min(a // x, b // y)
    print(answer)

__starting_point()

import fractions

a, b, x, y = list(map(int, input().split()))

d = fractions.gcd(x, y)
x //= d
y //= d
ans = min(a // x, b // y)
print(ans)


def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)

a, b, x, y = map(int, input().split())

g = gcd(x, y)
x //= g
y //= g

print(min(a//x, b//y))

from sys import stdin,stdout,exit
def sin(): 
	return stdin.readline().rstrip()
def listInput():
	return list(map(int,sin().split()))
def printBS(li):
	if not li: return
	for i in range(len(li)-1):
		stdout.write("%d "%(li[i]))
	stdout.write("%d\n"%(li[-1]))

a,b,x,y = listInput()
from fractions import gcd
g = gcd(x,y)
x//=g
y//=g
print(min(a//x,b//y))

"""#T=int(input())
#for i in range(0,T):
N=int(input())
#a,b=map(int,input().split())
s=[int(x) for x in input().split()]
mn=min(s)
mx=max(s)
diff=mx-mn+1
ans=diff-len(s)
print(ans)
#for j in range(0,len(s)):"""


import math
a,b,x,y=list(map(int,input().split()))
g=math.gcd(x,y)
x=x//g
y=y//g
a1=a//x
a2=b//y
ans=min(a1,a2)
print(ans)
    


from math import gcd
a,b,x,y=map(int,input().split())
r=gcd(x,y)
x//=r;y//=r
print(min(a//x,b//y))

from fractions import gcd
a,b,x,y = list(map(int,input().split()))

gcd_val = gcd(x, y)
x //= gcd_val
y //= gcd_val

print(min(a//x,b//y))


from math import gcd

a, b, x, y = map(int, input().split(' '))

g = gcd(x, y)

n1 = (a*g)//x
n2 = (b*g)//y

print(min(n1,n2))

def gcd(a, b):
    while (b != 0):
        x = a % b
        a = b
        b = x
    return a

a, b, x, y = list(map(int, input().strip().split(' ')))

d = gcd(x, y)
x1 = x // d
x2 = y // d

print(min(a//x1, b//x2))


import sys
from fractions import Fraction
a,b,x,y=list(map(int,sys.stdin.readline().strip().split()))
f=str(Fraction(x,y)).split('/')
if(len(f)==1):
    x=int(f[0])
    y=1
else:
    x=int(f[0])
    y=int(f[1])

print(min(int(a/x),int(b/y)))