Problem D
Dwindling Discounts

You are at a street market that just opened for the day. There are $N$ items you want to buy, each sold at a different stall. Stall $i$ has an item with a base price of $p_i$ coins. However, as the day goes on and more customers show up, each stall raises its price by $r_i$ coins per minute.

The market is crowded, so purchasing the item at stall $i$ takes $d_i$ minutes. You can only be at one stall at a time, and once you start a purchase you must complete it before moving on. The price you pay for an item is its base price plus the accumulated price increase at the moment you begin purchasing it. In other words, if you begin buying item $i$ at time $T$, you pay $p_i + r_i \cdot T$.

You arrive at time $0$ and want to buy all $N$ items. What is the minimum total cost?

Input

The first line contains a single integer $N$, the number of items.

Each of the following $N$ lines contains three integers $p_i$, $r_i$ and $d_i$: the base price, the rate of price increase per minute, and the time in minutes to purchase item $i$.

Output

Output a single integer: the minimum total cost.

Limits

• $1 \leq N \leq 200\, 000$

• $1 \leq p_i \leq 10\, 000$

• $1 \leq r_i \leq 10\, 000$

• $1 \leq d_i \leq 10\, 000$

3
10 3 2
20 5 1
15 2 4

54

2
1 5 10
1 3 1

7