G-Gorgeous Andrea_第四届南方科技大学程序设计竞赛同步赛

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Andrea loves collecting pebbles.

She has $N (1\leq N\leq 500000)$ pebbles labeled from $1$ to $N$ .

The pebble labeled $i$ has its lovely value $a_i$ , lively value $b_i$ , and lucky value $c_i$ $(|a_i|,|b_i|\leq 10^6,\ |c_i|\leq 10^{12})$ .

She wants to select some pebbles.

If she chooses $k$ pebbles labeled $p_1, p_2, \dots, p_k$ $(1 \leq p_1 < p_2 < \dots < p_k \leq N)$ , the happy value she can obtain will be

$\sum_{i=1}^{k}c_{p_i}+\sum_{i=2}^{k} a_{p_{i}}\cdot b_{p_{i-1}}$

Andrea wants to know the maximal happy value she can obtain.

Andrea must pick at least one pebble.

The input consists of:

One line containing one integer $N$ .

Each of the next $N$ lines contains three integers $a_i,b_i,c_i$ .

Output the answer.

示例1

复制

复制

For sample 1, Andrea could select pebble 1 and 4. The corresponding happy value is

示例2

复制

3
-91 -24 -10
-32 14 -10
-56 23 -70

复制

For sample 2, Andrea could select pebble 1 and 3. The corresponding happy value is