solving linear program with 2 variables

from __future__ import division

c, p, q, r, s = map(int, raw_input().split())
inf = float('inf')

def solve1(c, a, b, L, U):
    U = min(U, b // a)
    if c >= 0:
        return U
    else:
        return max(0, L)

def solve(c1, c2, a1, a2, b, L, U):
    if b < 0:
        return (-inf, -inf)
    def value((x, y)):
        return c1 * x + c2 * y
    if c1 <= 0:
        return (L, solve1(c2, a2, b - a1 * L, 0, inf))
    elif c2 <= 0:
        return (solve1(c1, a1, b, L, U), 0)
    elif a1 == 0:
        return (U, solve1(c2, a2, b, 0, inf))
    elif a2 == 0:
        return (0, inf)
    elif L == U:
        return (L, solve1(c2, a2, b - a1 * L, 0, inf))
    elif b == 0:
        return (0, 0)
    else:
        if U != inf:
            U = min(U, b // a1)
        if L != 0 or U != inf:
            xp, yp = solve(c1, c2, a1, a2, b - ((b - a1 * U + a2 - 1) // a2) * a2 - a1 * L, 0, inf)
            xp += L
            yp += (b - a1 * U + a2 - 1) // a2
            return max((U, (b - a1 * U) // a2), (xp, yp), key=value)
        if a1 < a2:
            x, y = solve(c2, c1, a2, a1, b, 0, inf)
            return y, x
        k = a1 // a2
        p = a1 - k * a2
        x, y = solve(c1 - c2 * k, c2, p, a2, b - k * (b // a1) * a2, 0, b // a1)
        y -= k *x
        y += (b // a1) * k
        return x, y

x, y = solve(p, q, r, s, c, 0, inf)
print x * p + q * y