P14167 [Algo Beat Contest 002.5 B] 草莓小蛋糕 (cakes)

**请 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 获得的最大美味值。

**【数据范围】** | 测试点编号 | $N \le$ | $C_i \le $ | $X_i$ 是否均为 $0$ | | :---------: | :-----: | :--------: | :-----------: | | $1 \sim 2$ | $10$ | $100$ | 否 | | $3 \sim 5$ | $10$ | $10^5$ | 否 | | $6 \sim 7$ | $10^3$ | $100$ | 否 | | $8 \sim 10$ | $10^3$ | $10^5$ | 否 | | $11 \sim 15$ | $10^5$ | $100$ | 否 | | $16 \sim 17$ | $10^5$ | $10^5$ | 是 | | $18 \sim 25$ | $10^5$ | $10^5$ | 否 | 对于所有数据，保证： - $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` 进行输入输出，需要手写读写函数，具体模板如下： ```cpp #include 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