A sweet little monster Om Nom loves candies very much. One day he found himself in a rather tricky situation that required him to think a bit in order to enjoy candies the most. Would you succeed with the same task if you were on his place? [Image] 

One day, when he came to his friend Evan, Om Nom didn't find him at home but he found two bags with candies. The first was full of blue candies and the second bag was full of red candies. Om Nom knows that each red candy weighs W_{r} grams and each blue candy weighs W_{b} grams. Eating a single red candy gives Om Nom H_{r} joy units and eating a single blue candy gives Om Nom H_{b} joy units.

Candies are the most important thing in the world, but on the other hand overeating is not good. Om Nom knows if he eats more than C grams of candies, he will get sick. Om Nom thinks that it isn't proper to leave candy leftovers, so he can only eat a whole candy. Om Nom is a great mathematician and he quickly determined how many candies of what type he should eat in order to get the maximum number of joy units. Can you repeat his achievement? You can assume that each bag contains more candies that Om Nom can eat.


-----Input-----

The single line contains five integers C, H_{r}, H_{b}, W_{r}, W_{b} (1 ≤ C, H_{r}, H_{b}, W_{r}, W_{b} ≤ 10^9).


-----Output-----

Print a single integer — the maximum number of joy units that Om Nom can get.


-----Examples-----
Input
10 3 5 2 3

Output
16



-----Note-----

In the sample test Om Nom can eat two candies of each type and thus get 16 joy units.

Difficulty: interview

Starter code:

Solutions:
import sys
f = sys.stdin

C, Hr, Hb, Wr, Wb = map(int, f.readline().strip().split())

if Hr/Wr < Hb/Wb:
    Hr, Hb, Wr, Wb = Hb, Hr, Wb, Wr

if (C % Wr) == 0 and (C // Wr) > 0:
    print((C // Wr)*Hr)
    
elif (C // Wr) == 0:
    print((C // Wb)*Hb)

else:
    nmax =  (C // Wr)
    pmax = nmax*Hr + ((C - nmax*Wr) // Wb) * Hb
    dmax = ((C - (nmax-0)*Wr) % Wb)
    #print(0, pmax, dmax)
    
    #
    #pm1 = (nmax-1)*Hr + ((C - (nmax-1)*Wr) // Wb) * Hb 
    #if pm1>pmax:
    #    pmax = pm1
    if  Hr/Wr > Hb/Wb:
        dx = dmax * (Hb/Wb) / (Hr/Wr - Hb/Wb)    
    elif  Hr/Wr < Hb/Wb: 
        dx = 0 
    else:
        dx = Wb * Wr
        if Wr<Wb:
            nmax =  (C // Wb)
            pmax = nmax*Hb + ((C - nmax*Wb) // Wr) * Hr   
        if Wr>Wb:
            nmax =  (C // Wr)
            pmax = nmax*Hr + ((C - nmax*Wr) // Wb) * Hb   
            
    if Wr>Wb and dx>0:    
        for k in range(1, C//Wr):
            if k*Wr > dx:
                break
            pk = (nmax-k)*Hr + ((C - (nmax-k)*Wr) // Wb) * Hb 
            dk = ((C - (nmax-k)*Wr) % Wb)
            #print(k, pmax, pk, dk)
            if pk>pmax:
                pmax = pk
            if dk==0 :
                break
    elif Wr<Wb and dx>0:   
        for j in range(1, C//Wb+1):
            k = nmax - (C-j*Wb)//Wr
            if k*Wr > dx:
                break
            
            pk = (nmax-k)*Hr + ((C - (nmax-k)*Wr) // Wb) * Hb 
            dk = ((C - (nmax-k)*Wr) % Wb)
            #print(j, k, pmax, pk, dk, (nmax-k), ((C - (nmax-k)*Wr) // Wb) )
            if pk>pmax:
                pmax = pk
                #dmax = dk
            if dk==0 :
                break            
            
#    elif Wr<Wb and dx>0:   
#        for j in range(1, C//Wb+1):
#            k = (j*Wb - dmax)//Wr
#            if k*Wr > dx:
#                break
#            pk = (nmax-k)*Hr + ((C - (nmax-k)*Wr) // Wb) * Hb 
#            dk = ((C - (nmax-k)*Wr) % Wb)
#            print(j, k, pmax, pk, dk, (nmax-k), ((C - (nmax-k)*Wr) // Wb) )
#            if pk>pmax:
#                pmax = pk
#                #dmax = dk
#            if dk==0 :
#                break
            
    print(pmax)    

m, h1, h2, w1, w2 = map(int, input().split())
if h2 / w2 > h1 / w1:
    h1, h2 = h2, h1
    w1, w2 = w2, w1
if w1 ** 2 >= m:
    res = 0
    for i in range(int(m ** 0.5 + 1)):
        if i * w1 <= m:
            new = i * h1 + (m - w1 * i) // w2 * h2
            res = max(res, new)
    print(res)
    return
res = 0
for i in range(int(m ** 0.5 + 5)):
    new_res = i * h2 + ((m - i * w2) // w1) * h1
    res = max(res, new_res)
print(res)

a, b, c, d, e = list(map(int, input().split(' ')))
check = int(a**0.5)

#red candy
#height b
#weight d

#blue candy
#height c
#weight e

ans = 0
for red in range(check+1):
    blue = (a-d*red)//(e)
    if blue >= 0:
        ans = max(ans, red*b+blue*c)

for blue in range(check+1):
    red = (a-e*blue)//(d)
    if red >= 0:
        ans = max(ans, red*b+blue*c)

print(ans)

c, hr, hb, wr, wb = map(int, input().split())
s = 0

if wb < wr: hr, hb, wr, wb = hb, hr, wb, wr
if wb * wb > c:
    for nb in range(c // wb + 1):
        s = max(s, nb * hb + hr * ((c - wb * nb) // wr))
else:
    if hr * wb < hb * wr: hr, hb, wr, wb = hb, hr, wb, wr

    for nb in range(min(31625, c // wb + 1)):
        s = max(s, nb * hb + hr * ((c - wb * nb) // wr))
print(s)

import math
def solve(c,hr,hb,wr,wb):
    INF = math.ceil(math.sqrt(c))
    if wb > wr:
        wb,wr = wr,wb
        hb,hr = hr,hb
    if wr > INF:
        ans = 0
        i = 0
        while i * wr <= c and i < INF:
            ans = max(ans,i * hr + ((c - i * wr) // wb) * hb)
            i+=1
        return ans
    else:
        if wr * hb > hr * wb:
            wb,wr = wr,wb
            hb,hr = hr,hb
        ans = 0
        j = 0
        while j * wb <= c and j <= wr:
            ans = max(ans,j * hb + ((c - j * wb) // wr) * hr)
            j+=1
        return ans

c,hr,hb,wr,wb = list(map(int,input().split()))
print(solve(c,hr,hb,wr,wb))


__author__ = 'trunghieu11'

def calc(n, h1, h2, w1, w2):
    answer = 0
    len = n // w1
    for i in range(0, min(len, 100000) + 1):
        answer = max(answer, i * h1 + (n - i * w1) // w2 * h2)
    return answer

n, hR, hB, wR, wB = map(int, input().split())
print(max(calc(n, hR, hB, wR, wB), calc(n, hB, hR, wB, wR)))

def main():
    c, hr, hb, wr, wb = (int(i) for i in input().split())

    if wb < c**(1/2) > wr:
        if hr / wr < hb / wb:
            wr, hr, wb, hb = wb, hb, wr, hr
        mx = 0
        for i in range(wr + 1):
            tmx = i * hb + ((c - i * wb) // wr) * hr
            mx  = tmx if tmx > mx else mx
    else:
        if wr <= wb:
            wr, hr, wb, hb = wb, hb, wr, hr
        nr = 0
        mx = 0
        while nr * wr <= c:
            tmx = nr * hr + ((c - nr * wr) // wb) * hb
            mx = tmx if tmx > mx else mx
            nr += 1

    print(mx)


def __starting_point():
    main()

__starting_point()

import math
c,hr,hb,wr,wb = list(map(int,input().split()))
if wr < wb:
    wr, wb = wb, wr
    hr, hb = hb, hr
ans = 0
if wr * wr >= c:
    for i in range(c//wr+1):
        ans = max(ans, i*hr+(c-i*wr)//wb*hb)
else:
    if hr*wb < hb*wr:
        wr, wb = wb, wr
        hr, hb = hb, hr
    for i in range (wr):
        ans = max(ans, i*hb+(c-i*wb)//wr*hr)
print(ans)
        



import math
c,hr,hb,wr,wb = map(int,input().split())
if wr < wb:
    wr, wb = wb, wr
    hr, hb = hb, hr
ans = 0
if wr * wr >= c:
    for i in range(c//wr+1):
        ans = max(ans, i*hr+(c-i*wr)//wb*hb)
else:
    if hr*wb < hb*wr:
        wr, wb = wb, wr
        hr, hb = hb, hr
    for i in range (wr):
        ans = max(ans, i*hb+(c-i*wb)//wr*hr)
print(ans)

def main():
    c, hr, hb, wr, wb = map(int, input().split())
    ans = 0
    for i in range(10**6 + 1):
        if i * wr <= c:
            ans = max(ans, i * hr + ((c - i * wr) // wb) * hb)
        if i * wb <= c:
            ans = max(ans, i * hb + ((c - i * wb) // wr) * hr)
    print(ans)





main()

C, Hr, Hb, Wr, Wb = map(int, input().split())
ans = 0
for i in range(10 ** 5):
    if Wr * i <= C:
        ans = max(ans, Hr * i + (C - Wr * i) // Wb * Hb)
for i in range(10 ** 5):
    if Wb * i <= C:
        ans = max(ans, Hb * i + (C - Wb * i) // Wr * Hr)
print(ans)

C, Hr, Hb, Wr, Wb = map(int, input().split())
ans = 0
for i in range(3 * 10 ** 5):
    if Wr * i <= C:
        ans = max(ans, Hr * i + (C - Wr * i) // Wb * Hb)
for i in range(3 * 10 ** 5):
    if Wb * i <= C:
        ans = max(ans, Hb * i + (C - Wb * i) // Wr * Hr)
print(ans)

C, Hr, Hb, Wr, Wb = map(int, input().split())
ans = 0
for i in range(5 * 10 ** 5):
    if Wr * i <= C:
        ans = max(ans, Hr * i + (C - Wr * i) // Wb * Hb)
for i in range(5 * 10 ** 5):
    if Wb * i <= C:
        ans = max(ans, Hb * i + (C - Wb * i) // Wr * Hr)
print(ans)

import math
c,x,y,a,b = list(map(int,input().split()))
lim = int(math.sqrt(c))
ans = 0
for i in range(lim):
    if(c>=i*a):
        ans = max(ans,x*i+(c-i*a)//b*y)
    if(c>=i*b):
        ans = max(ans,y*i+(c-i*b)//a*x)
print(ans)





import math

c, hr, hb, wr, wb = map(int, input().split())
s = int(math.sqrt(c))
ans = 0
for i in range(s):
    if c >= i * wr:
        ans = max(ans, hr * i + (c - i * wr) // wb * hb)
    if c >= i * wb:
        ans = max(ans, hb * i + (c - i * wb) // wr * hr)

print(ans)

# -*- coding: utf-8 -*-

#max_grams = 10 
#weight_r = 3 
#joy_r = 5 
#weight_b = 2 
#joy_b = 3


def max_joy(max_grams, weight_r, joy_r, weight_b, joy_b, jollies, memoiser): 
    if max_grams < 0: 
        return 0
    
    if max_grams == 0: 
        return jollies
    
    if (str(max_grams) in memoiser): 
        if jollies >= memoiser[str(max_grams)]: 
            return 0
    
    memoiser[str(max_grams)] = jollies
    
    
    res1 = max_joy(max_grams - weight_r, weight_r, joy_r, weight_b, joy_b, jollies + joy_r, memoiser) 
    res2 = max_joy(max_grams - weight_b, weight_r, joy_r, weight_b, joy_b, jollies + joy_b, memoiser) 
    
    return max(res1, res2)

def main(): 
   # max_grams, weight_r, joy_r, weight_b, joy_b = [int(x) for x in input().split()]
    max_grams = 982068341 
    weight_r = 55 
    joy_r = 57 
    weight_b = 106 
    joy_b = 109
    memoiser = {}
    jollies = 0
    res = max_joy(max_grams, weight_r, joy_r, weight_b, joy_b, jollies, memoiser)
    print(res)

#main()

import math
c,x,y,a,b = map(int,input().split())
lim = int(math.sqrt(c))
ans = 0
for i in range(lim):
    if(c>=i*a):
        ans = max(ans,x*i+(c-i*a)//b*y)
    if(c>=i*b):
        ans = max(ans,y*i+(c-i*b)//a*x)
print(ans)

C, Hr, Hb, Wr, Wb = list(map(int, input().split()))

ans = 0

for i in range(10 ** 5):

    if Wr * i <= C:

        ans = max(ans, Hr * i + (C - Wr * i) // Wb * Hb)

for i in range(10 ** 5):

    if Wb * i <= C:

        ans = max(ans, Hb * i + (C - Wb * i) // Wr * Hr)

print(ans)



# Made By Mostafa_Khaled


C, Pr, Pb, Wr, Wb = list(map(int, input().split()))
result = 0
if Wr * Wr >= C:
    i = 0
    while Wr * i <= C:
        j = int((C - Wr * i) / Wb)
        result = max(result, Pr * i + Pb * j)
        i += 1
    print(result)
    return

if Wb * Wb >= C:
    i = 0
    while Wb * i <= C:
        j = int((C - Wb * i) / Wr)
        result = max(result, Pb * i + Pr * j)
        i += 1
    print(result)
    return

Ab = Pb / Wb
Ar = Pr / Wr

if Ab < Ar:
    i = 0
    while i * i <= C:
        j = int((C - Wb * i) / Wr)
        result = max(result, Pb * i + Pr * j)
        i += 1
    print(result)
else:
    i = 0
    while i * i <= C:
        j = int((C - Wr * i) / Wb)
        result = max(result, Pr * i + Pb * j)
        i += 1
    print(result)