Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Om Nom and Candies

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA 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?

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2018 12:56:00 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|