Little Joty has got a task to do. She has a line of n tiles indexed from 1 to n. She has to paint them in a strange pattern.

An unpainted tile should be painted Red if it's index is divisible by a and an unpainted tile should be painted Blue if it's index is divisible by b. So the tile with the number divisible by a and b can be either painted Red or Blue.

After her painting is done, she will get p chocolates for each tile that is painted Red and q chocolates for each tile that is painted Blue.

Note that she can paint tiles in any order she wants.

Given the required information, find the maximum number of chocolates Joty can get.


-----Input-----

The only line contains five integers n, a, b, p and q (1 ≤ n, a, b, p, q ≤ 10^9).


-----Output-----

Print the only integer s — the maximum number of chocolates Joty can get.

Note that the answer can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.


-----Examples-----
Input
5 2 3 12 15

Output
39

Input
20 2 3 3 5

Output
51

Difficulty: interview

Starter code:

Solutions:
from fractions import gcd
def lcm(a, b):
    return a*b//gcd(a, b)
n, a, b, p, q = list(map(int, input().split(' ')))
red = n//a
blue = n//b
if (p<q):
    red -= n//lcm(a, b)
else:
    blue -= n//lcm(a, b)

print(p*red+q*blue)


3
# Copyright (C) 2016 Sayutin Dmitry.
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License as
# published by the Free Software Foundation; version 3
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; If not, see <http://www.gnu.org/licenses/>.

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

n, a, b, p, q = list(map(int, input().split()))

s = (n // a) * p + (n // b) * q
s -= (n // (a * b // gcd(a, b))) * min(p, q)
print(s)


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

n, a, b, p, q = map(int, input().split())
ox = n // (a * b // gcd(a, b))
ax = n // a - ox
bx = n // b - ox
print(ax * p + bx * q + ox * max(p, q))

from fractions import gcd
n,a,b,p,q=list(map(int,input().split()))
x=n//(a*b//gcd(a,b))
print((n//a-x)*p+(n//b-x)*q+x*max(p, q))


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

def lcm(a, b):
    return (a * b) // gcd(a, b)

def main():
    n, a, b, p, q = list(map(int, input().split()))
    if a == b:
        print((n // a) * max(p, q))
    else:
        print((n // a) * p + (n // b) * q - (n // lcm(a, b)) * min(p, q))

main()


#!/usr/bin/env python3

from fractions import gcd

try:
    while True:
        n, a, b, p, q = list(map(int, input().split()))
        print(n // a * p + n // b * q - n // (a // gcd(a, b) * b) * min(p, q))

except EOFError:
    pass


import math

n,a,b,p,q = [int(x) for x in input().split(' ')]

g = int(a * b / math.gcd(a,b))

if p > q: l = q
else: l = p
print((n//a)*p + (n//b)*q - (n//g)* l)

from fractions import gcd
def lcm(x, y):
    return x * y // gcd(x, y)

n, a, b, p, q = list(map(int, input().split()))

ans = p * (n // a)
ans += q * (n // b)
ans -= min(p, q) * (n // lcm(a, b))
print(ans)


def lcm(a, b):
    x = a * b
    while b != 0:
        (a, b) = (b, a % b)
    return x // a


n, a, b, p, q = map(int, input().split())
print(n // a * p + n // b * q - n // lcm(a, b) * min(p, q))

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

n, a, b, p, q = map(int, input().split())
if (p > q):
    c1 = p
    p = q
    q = c1
    c = a
    a = b
    b = c
t = (a // gcd(a, b)) * b
print(int((n // a) * p + (n // b) * q - (n // t) * p))

n, a, b, p, q = list(map(int, input().split()))
from fractions import gcd
ans = (n // a) * p + (n // b) * q
l = (a * b) // gcd(a, b)
ans -= (n // l) * (min(p, q))
print(ans)


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

def get_nok(a, b):
	return (a * b) // gcd(a, b)

n, a, b, p, q = list(map(int, input().split()))

if p < q:
	a, b = b, a
	p, q = q, p


nok = get_nok(a, b)

t = n // a
minus = n // nok
c = n // b
print(t * p + q * (c - minus))




n,a,b,p,q = list(map(int,input().split()))
a2 = a
b2 = b
while b2 != 0 :
    a2,b2 = b2,a2%b2

print(n // a * p + n // b * q - n // ((a*b) // a2) * (min(p,q)))


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

n, a, b, p, q = [int(i) for i in input().split()]
lcm = a * b // gcd(a,b)
onlyA = n//a - n//lcm
onlyB = n//b - n//lcm
print(p * onlyA + q * onlyB + max(p,q) * (n // lcm))


#C
cin=lambda:map(int,input().split())
n,a,b,p,q=cin()

def lcm(a,b):
    m = a*b
    while a != 0 and b != 0:
        if a > b:
            a %= b
        else:
            b %= a
    return m // (a+b)

if p>=q:
    res=(n//a)*p + (n//b-n//lcm(a,b))*q
else:
    res=(n//b)*q + (n//a-n//lcm(a,b))*p
print(res)

n, a, b, p, q = map(int ,input().split())

red_max = n // a
blue_max = n // b

import fractions

gcd = (a*b) // fractions.math.gcd(a, b)
commons = n // gcd

if p > q:
    print(red_max*p + (blue_max-commons)*q)
else:
    print((red_max-commons)*p + blue_max*q)

from fractions import gcd
n, a, b, p, q = map(int, input().split())
k = (a*b)//gcd(a, b)
divisors_a = n//a
divisors_b = n//b
divisors_k = n//k
print(max((divisors_a - divisors_k)*p + divisors_b*q, (divisors_b - divisors_k)*q + divisors_a*p))

def gcd(a, b):
    if b < 1:
        return a
    if b > a:
        return gcd(b, a)
    return gcd(b, a % b)

n, a, b, p, q = list(map(int, input().split()))
l = [n // a, n // b, n // (a * b // gcd(a, b))]
print((l[0] - l[2]) * p + (l[1] - l[2]) * q + l[2] * max(p, q))
#print(l[0], l[1], l[2])
#print(gcd(a, b))


from fractions import gcd
n,a,b,p,q = list(map(int,input().split()))
num1 = n//a
num2 = n//b
t = a*b//gcd(a,b)
num3 = n//t
print((num1-num3)*p + (num2-num3)*q + num3*max(p,q))


from math import gcd

n, a, b, p, q = map(int, input().split())
if p > q:
    p, q = q, p
    a, b = b, a
res = n // b * q
res += (n // a - n * gcd(a, b) // a // b) * p
print(res)

n, a, b, p, q = tuple(map(int, input().split()))

s = (n // a) * p
s += (n // b) * q

def gcd(p, q):
    if p < q:
        return gcd(q, p)
    if q == 0:
        return p
    return gcd(q, p % q)

c = n // ((a *b ) //gcd(a, b))
if p < q:
    s -= c * p
else:
    s -= c * q

print(s)

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

def lcm(a, b):
    return a * b // gcd(a, b)

n, a, b, p, q = map(int, input().split())
s = n // a * p + n // b * q - n // lcm(a, b) * min(p, q)
print(s)

def nod(a,b):
    if a*b>0:
        return nod(b,a%b)
    else:
        return a+b



n,a,b,p,q = (int(i) for i in input().split())
print(n//a*p+n//b*q-n//(a*b//nod(a,b))*min(p,q))