Newbie Little H is playing a game with his $n$ friends!

The game they are playing involves flipping coins. Little H and his opponent each flip a coin; if the value of Little H's coin is greater than or equal to his opponent's, Little H wins; otherwise, the opponent wins.

The $i$-th friend has a coin with two sides showing $a_i$ and $b_i$. They bet $x_i$ coins against Little H, meaning if Little H wins, he gains $x_i$ coins, and if he loses, he loses $x_i$ coins.

Little H does not have a coin yet, so he can go to the evil craftsman Big D to customize one. If the two sides of the coin Little H obtains are $a$ and $b$, both $a$ and $b$ must be positive integers, and he must pay $ab$ coins.

Little H wants to know the maximum expected number of coins he can earn if he chooses an appropriate coin.

Note that Little H is very wealthy; he has enough coins initially, so there is no need to consider cases where he cannot afford the payment.

Input

The first line contains an integer $n$, representing the number of friends.

The next $n$ lines each contain three integers $a_i, b_i, x_i$, representing the two sides of the opponent's coin and the bet amount, respectively.

Output

Output a single integer representing the expected number of coins Little H earns multiplied by $4$. It can be proven that this is always an integer. Note that losing coins is considered earning a negative number of coins.

Examples

Input 1

2
1 4 15
3 5 10

Output 1

10

Note 1

The coin created has sides $1$ and $5$.

Input 2

1
2 2 8

Output 2

16

Input 3

See ex_game3.in and ex_game3.ans in the provided files. This sample satisfies the special constraints for test cases $1 \sim 4$.

Input 4

See ex_game4.in and ex_game4.ans in the provided files. This sample satisfies the special constraints for test cases $5 \sim 9$.

Constraints

For all data, it is guaranteed that $1 \leq n \leq 5\cdot 10^5$ and $1 \leq a_i, b_i, x_i \leq 10^9$.