Little H and his $n$ friends are playing a game!
The game 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 the 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. That is, if Little H wins, he gains $x_i$ coins; otherwise, he loses $x_i$ coins.
Little H does not have a coin yet, so he can go to the evil craftsman D to customize one. If the two sides of the coin Little H gets are $a$ and $b$, then 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 the case 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 values on the two sides of the opponent's coin and the bet amount, respectively.
Output
Output a single integer representing the result of the maximum expected coins Little H can earn 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
Constraints
| Subtask | $n\leq$ | Special Properties | Score |
|---|---|---|---|
| $1$ | $100$ | None | $3$ |
| $2$ | $2000$ | None | $21$ |
| $3$ | $5\times 10^5$ | $a_i, b_i, x_i$ are randomly generated in $[1, 10^9]$ | $34$ |
| $4$ | $5\times 10^5$ | None | $42$ |
For all data, it is guaranteed that $1\leq n\leq 5\times 10^5$ and $1\leq a_i, b_i, x_i\leq 10^9$.