Training Site # Shopping List

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 1.0 seconds

Ah, it's shopping day! You have $N$ food items you want to buy and how much of each item you want, $W$.

Unfortunately, your favourite supermarkets, Countup, and PAK'nSPEND, both have a limited amount of each food item in stock, $A$ and $B$ respectively. Each supermarket has their own price for each item $X$, and $Y$, respectively.

You need to figure out the minimum cost to buy all the food you want.

## Input

• The first line contains the integer $N$, the number of food items you want.
• The next $N$ lines each contain five space-separated integers, $W$, the amount of that item you want, $A$ and $X$, the amount and cost at Countup, and $B$ and $Y$, the amount and cost at PAK'nSPEND.
You may assume that $W \leq A + B$ which means there will always be enough in stock to satisfy your shopping needs.

## Output

Output a single integer – the minimum cost to buy all your food.

## Constraints

• $1 \leq N \leq 100$
• $1 \leq W \leq 100$
• $0 \leq A, B \leq 100$
• $0 \leq X, Y \leq 100$

• Subtask 1 (30%): $X = Y$ for all items
• Subtask 2 (30%): $A = B = 100$ for all items
• Subtask 3 (40%): No further constraints apply
• ### Sample Input 1

1
8 5 10 6 10


### Sample Output 1

80

• ### Sample Input 2

2
1 100 3 100 4
1 100 5 100 4


### Sample Output 2

7

• ### Sample Input 3

1
4 2 3 100 5


### Sample Output 3

16