Baked Goods

Interview

Time limit1sMemory limit1024 MB

Summary

Given a budget S and two cupcake types, each with an ingredient cost and a profit, find the maximum total profit from an affordable whole-number mix of the two.

Level: Medium6 of 10
Topics: Brute force, Math
Solved: No attempts yet

Problem

Ugnė decided to bake two kinds of cupcakes for the school bake sale.

From her mother's secret recipes, she knows how much of each ingredient she needs. She has calculated that the ingredients for one cupcake of the first kind cost a euros, and for one of the second kind cost b euros.

She earns A euros of profit for each sold cupcake of the first kind and B euros for each of the second kind. Before she starts her baking career, she has to buy the products needed for baking.

Ugnė wants to know the greatest profit she could earn by selling her cupcakes, if her mother gives her S euros to buy the products. She is sure she can sell every cupcake she bakes.

Input

The first line contains one integer S, the money Ugnė can spend on making cupcakes. She cannot buy new ingredients with the money she earns from selling cupcakes.

The second line contains two integers: the cost a and the profit A of one cupcake of the first kind.

The third line contains two integers: the cost b and the profit B of one cupcake of the second kind.

Output

Print one integer, the greatest profit Ugnė can earn by selling cupcakes. Money set aside for buying ingredients but not used does not count toward the final answer.

Constraints

$1 \le S \le 1\,000\,000\,000$
$1 \le a, A, b, B \le 1\,000\,000$

The correct answer never exceeds $2\,000\,000\,000$ .

Examples1

Example 1
Input
```
105
70 40
30 20
```
Expected output
```
60
```