The Recipe

You have decided to cook dinner. The dish you are going to make requires $N$ ingredients. For each ingredient, you know the amount of it you have at home, the amount you need in total and how much one unit of the ingredient costs if you need to buy it. You need to purchase the extra amount you need for each ingredient. Your task is to compute the total cost to purchase what you need for your meal.

Input

The first line contains an integer $N$ ($1 \le N \le 5$), the number of ingredients.

The following $N$ describe an ingredient with three integers $H, B, K$ (all between $0$ and $500$ the amount you have, the amount you need, and the cost for each unit of the ingredient.

Output

Output a single integer – the total cost for the ingredients.

Scoring

Your program will be tested on three test cases. If it passes two of them, you will be given $50$ points. If it passes all three of them, you will be given $100$ points.

In two of the test cases, $n \le 15$.

3
10 5 1000
0 4 5
2 5 1

23