你是杂货店的老板，店里有 $n$ 件商品。每件商品 $i$ 都有一个关联的重量 $w_i$、初始体积 $v_i$ 和压缩系数 $c_i$。

你将所有商品堆成一堆以保持店面整洁。由于商品可以被压缩，假设商品 $i$ 上方所有物品的重量之和为 $W$（不包含商品 $i$ 本身），那么堆叠后，商品 $i$ 的实际体积将变为 $v_i - c_i \times W$。

由于店里的空间非常有限，你想要知道所有物品实际体积之和的最小值。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示商品的数量。

接下来的 $n$ 行，每行包含三个整数 $w_i, v_i, c_i$ ($1 \le w_i \le 10^5, 1 \le v_i \le 10^{12}, 0 \le c_i < \frac{v_i}{\sum w_i}$)，分别表示第 $i$ 件商品的重量、体积和压缩系数。

保证每件商品的实际体积在压缩后永远不会变为负数或零。

输出格式

输出一个整数，表示答案。

样例

样例输入 1

3
1 8 1
2 9 2
3 10 2

样例输出 1

16

说明

一种可能的最佳方案是，从下到上堆叠商品的顺序为 1, 2, 3。商品 1 的实际体积为 $8 - 1 \times (2 + 3) = 3$；商品 2 的实际体积为 $9 - 2 \times 3 = 3$；商品 3 的实际体积为 $10$，因为其上方没有其他商品。