J. Stacking of Goods
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

You are a grocery store owner, and there are $$$n$$$ goods in your store. Each good $$$i$$$ has an associated weight $$$w_i$$$, initial volume $$$v_i$$$, and compression coefficient $$$c_i$$$.

You stack all the goods into one pile to keep the store tidy. Because goods can be compressed, assuming that the sum of the weights of the items above the goods $$$i$$$ is $$$W$$$ (Not including itself), then after stacking, the actual volume of the goods $$$i$$$ will become $$$v_i-c_i\times W$$$.

The space in your store is really limited, so you want to know the minimum possible value of the sum of the actual volumes of the items.

Input

The first line contains a single integer $$$n\ (1\le n\le 10^5)$$$, representing the number of goods.

For the following $$$n$$$ lines, each line contains three integers $$$w_i, v_i, c_i\ (1\le w_i\le 10^5, 1\le v_i\le 10^{12},0\le c_i \lt \frac{v_i}{\sum w_i})$$$, representing the weight, volume, and compression coefficient of the $$$i$$$-th good.

It's guaranteed that the actual volume of each good will never be compressed into a negative number or zero.

Output

A single integer represents the answer.

Example
Input
3
1 8 1
2 9 2
3 10 2
Output
16
Note

A possible optimal solution is that the order of goods in the pile from bottom to top is $$$1,2,3$$$. The actual volume of good $$$1$$$ is $$$8-1\times (2+3)=3$$$; the actual volume of good $$$2$$$ is $$$9-2\times 3=3$$$; and the actual volume of good $$$3$$$ is $$$10$$$ since there are no other goods above it.