Gathering Mushrooms

Many kinds of mushrooms grow in the forest of Byteland. Recently a famous mushroom picker, Mr. Stanislaw, discovered a delicious new species and named it the Stasiek.

A Stasiek is special because you can easily predict how much its weight grows each day. Unfortunately, every mushroom turns poisonous after a certain number of days and can no longer be eaten. Fortunately, Mr. Stanislaw can tell, just by looking at a mushroom, after how many days it will become inedible.

Today Mr. Stanislaw walked through the forest and wrote down the data of every mushroom he saw. Now he wonders after how many days he should come back in order to collect as much mushroom weight as possible. If several days are equally good, he always picks the earliest one. His wife also forbids him from visiting the forest twice in one day, so he cannot come back after $0$ days (that is, today).

Each mushroom $i$ weighs $m_i$ today (day $0$) and its weight grows by $p_i$ every day. The mushroom stays edible for $d_i$ days counting from today, that is on days $0, 1, \dots, d_i - 1$, and becomes poisonous on day $d_i$. Therefore, if Mr. Stanislaw comes back on a day $t \ge 1$, only the mushrooms with $t < d_i$ are edible, and such a mushroom then weighs $m_i + p_i \cdot t$.

On the day he returns, Mr. Stanislaw collects the total weight of every mushroom that is still edible. Find the day $t \ge 1$ that maximizes this total weight. If several days give the maximum, the answer is the earliest of them.

The first line contains the number of mushrooms $n$ ($1 \le n \le 10^6$).

Each of the next $n$ lines describes one mushroom with three space-separated integers $m$, $p$, $d$ ($1 \le m, p, d \le 10^5$): the current weight, the daily weight gain, and the number of days the mushroom stays edible, respectively.

Print a single integer on one line: the number of days after which Mr. Stanislaw should return so that the collected mushroom weight is as large as possible. If the maximum is reached on several days, print the earliest one.

Suppose there are three mushrooms with $(m, p, d) = (1, 1, 2)$, $(5, 5, 3)$, $(7, 2, 4)$. The total weight of the edible mushrooms on each possible return day is:

• after $1$ day: the three mushrooms weigh $(2, 10, 9)$, summing to $21$;
• after $2$ days: the first mushroom is poisonous and cannot be eaten, the remaining two weigh $(15, 11)$, summing to $26$;
• after $3$ days: only the third mushroom is edible, weighing $13$;
• after $4$ days: no mushroom is edible, so the sum is $0$.

The total weight of edible mushrooms is largest, $26$, after $2$ days, so the answer is $2$.