Public Judge

pjudge

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
Statistics

题目描述

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

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

第 $i$ 个好朋友有一个两面分别为 $a_i$ 和 $b_i$ 的硬币,他和小 H 赌 $x_i$ 个钢镚,即如果小 H 赢则他获得 $x_i$ 个钢镚,否则失去 $x_i$ 个钢镚。

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

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

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

输入格式

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

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

输出格式

一行一个整数,表示小 H 期望挣到的钢镚乘上 $4$ 后的结果,可以证明这一定是一个整数。注意亏钢镚被认为是挣了负数个钢镚。

样例一

input

2
1 4 15
3 5 10

output

10

explanation

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

样例二

input

1
2 2 8

output

16

样例三

见下发文件中的 ex_game3.inex_game3.ans ,该样例符合测试点 $1\sim 4$ 的特殊限制。

样例四

见下发文件中的 ex_game4.inex_game4.ans ,该样例符合测试点 $5\sim 9$ 的特殊限制。

数据范围与提示

测试点编号 $n\leq$ 特殊性质
$1\sim 4$ $100$
$5\sim 9$ $2000$
$10\sim 13$ $5\cdot 10^5$ $a_i,b_i,x_i$ 在 $[1,10^9]$ 中随机生成
$14\sim 20$ $5\cdot 10^5$

对于所有数据,保证 $1\leq n\leq 5\cdot 10^5$,$1\leq a_i,b_i,x_i\leq 10^9$。

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$