Shopping List

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$

Subtasks

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