题目背景

请 C++ 选手留意题面最下面的内容。

---

那天，初夏的气息漫进窗棂时，小 L 眼神柔得像化了的奶油，深情地看着小 Y，声音如流水般细腻。

“宝宝，你是我的草莓小蛋糕。”

可如今，当初那双眼底的亮泽早散了，那句裹着甜意的话也落了灰。这段曾浸着草莓香气的真挚感情，终究像放久的蛋糕般，没了当初的鲜活，再也不复存在了。

“希望我们以后不要再有交集。”

但是以后，真的就是永远吗。

题目描述

小 Z 有 $N$ 种草莓小蛋糕，其中第 $i$ 种小蛋糕有 $C_i$ 块，第一天的美味值为 $D_i$。由于小蛋糕会变质，之后的每一天，小蛋糕的美味值都会降低 $X_i$。即第 $m$ 天第 $i$ 种的一块小蛋糕的美味值为 $D_i-(m-1)X_i$。

从第一天起，小 Z 每天都可以选择一块小蛋糕并吃掉它，他就可以获得这个蛋糕当前的美味值。

由于不能浪费食物，即使美味值降为负数，小 Z 也必须吃完所有蛋糕。他想知道他最多能获得多少美味值。

输入格式

第一行一个正整数 $N$，表示小蛋糕的种数。

接下来 $N$ 行，每行三个整数 $C_i,D_i$ 和 $X_i$，表示第 $i$ 种蛋糕的数量，初始美味值以及每天降低的美味值。

输出格式

一行一个整数，表示小 Z 获得的最大美味值。

2
1 3 3
2 2 2

1

2
29 49 99
49 29 99

-294455

1
100000 1000000000000000 1000

99999995000050000000

提示

【数据范围】

测试点编号	$N \le$	$C_i \le$	$X_i$ 是否均为 $0$
$1 \sim 2$	$10$	$100$	否
$3 \sim 5$		$10^5$
$6 \sim 7$	$10^3$	$100$
$8 \sim 10$		$10^5$
$11 \sim 15$	$10^5$	$100$
$16 \sim 17$		$10^5$	是
$18 \sim 25$			否

对于所有数据，保证：

• $1 \le N \le 10^5$。
• $\boldsymbol{1 \le C_i \le 10^5}$。
• $1 \le D_i \le 10^{15}$。
• $0 \le X_i \le 10^3$。

---

C++ 选手请注意，由于答案可能超过 long long 的范围，请使用 __int128 存储答案，其用法如下：

__int128 的存储整数范围为 $-2^{127} \sim 2^{127}-1$，其运算等用法与 int 等整型数据类型的用法几乎一致，但无法用 cin/cout 进行输入输出，需要手写读写函数，具体模板如下：

#include <bits/stdc++.h>

using namespace std;

__int128 x; // 定义一个 __int128 类型的数

// 读入 __int128 的函数，会返回读入的数。
__int128 read() {
    char c;
    bool isf = 0;
    while (!isdigit(c = getchar())) {
    	isf = (c == '-');
    }
    __int128 res = (c ^ 48);
    while (isdigit(c = getchar())) {
    	res = (res << 3) + (res << 1) + (c ^ 48);
    }
    return isf ? -res : res;
}

// 输出 __int128 的函数。需传入需要输出的数作为参数。
void write(__int128 x) {
    if (x < 0) {
    	putchar('-'), x = -x;
    } 
    if (x >= 10) {
    	write(x / 10);
    }
    putchar('0' + x % 10);
}

int main() {
	x = read(); // 读入
	write(x); // 输出
	return 0;
}

注：2024 年联合省选 T1 告诉了我们一个教训，在 C++14 的编译环境下，__int128 不可以用 abs() 取绝对值，否则会 CE。