题目描述

萌新小 H 和他的 $n$ 个好朋友玩游戏！

他们将要玩的游戏是抛硬币。小 H 和他的对手分别抛出硬币，如果小 H 抛出的数值大于等于对方的，则小 H 赢，否则对手赢。

第 $i$ 个好朋友有一枚两面分别为 $a_i$ 和 $b_i$ 的硬币，他和小 H 赌 $x_i$ 个钢镚。也就是说：如果小 H 赢，则小 H 获得 $x_i$ 个钢镚；否则小 H 失去 $x_i$ 个钢镚。

小 H 还没有硬币，他可以去邪恶工匠大 D 那里定制一枚硬币。若小 H 得到的硬币两面分别是 $a,b$，则 $a,b$ 都需要是正整数，并且他需要支付 $ab$ 个钢镚。

小 H 想知道，如果他选择一枚合适的硬币，他期望最多能挣到多少钢镚。

注意，小 H 很富有，他初始有足够多的钢镚，不需要考虑钢镚不足以支付的情况。

输入格式

第一行一个整数 $n$，表示好朋友个数。

接下来 $n$ 行，每行三个整数 $a_i,b_i,x_i$，分别表示第 $i$ 个对手硬币两面的数字和赌资。

输出格式

一行一个整数，表示小 H 期望挣到的钢镚数乘以 $4$ 后的结果。

可以证明，这个值一定是整数。注意，亏钢镚被认为是挣了负数个钢镚。

样例一

输入

2
1 4 15
3 5 10

输出

10

解释

定制的硬币两面分别是 $1,5$。

样例二

输入

1
2 2 8

输出

16

数据范围与提示

子任务编号	$n\le$	特殊性质	分值
1	100	无	3
2	2000		21
3	$5\times 10^5$	$a_i,b_i,x_i$ 在 $[1,10^9]$ 中随机生成	34
4		无	42

对于所有数据，满足：

$$1\le n\le 5\times 10^5, \qquad 1\le a_i,b_i,x_i\le 10^9.$$