Lake Eleonora

The renowned band "Lake Eleonora" is planning a concert along a coordinate line.

In the country where the concert will take place, there are $n$ residents. The $i$-th resident lives at coordinate $x_i$, travels at a speed of one unit per $w_i$ seconds, and can hear the concert if it is held within $d_i$ units of their home.

The band needs to select an integer coordinate for the concert location. Residents who cannot hear the concert from their homes must travel to the concert site until they are within their hearing range (i.e., within $d_i$ units).

Your task is to help the band determine a location that minimizes the total travel time for all residents to reach a point where they can hear the concert. However, you should output the minimum possible total travel time, not the location itself.

Input

The first line contains a single integer $n$ ($1\le n\le 200,000$).

Each of the next $n$ lines contains three integers $x_i$, $w_i$, $d_i$ ($0\le x_i\le 10^9$, $1\le w_i\le 1,000$, $0\le d_i\le 10^9$).

Output

Output a single integer — the minimum possible total travel time.

Examples

Scoring

1. ($28$ points): $n,x_i,d_i\le 2,000$;

2. ($57$ points): $x_i,d_i\le 10^6$;

3. ($15$ points): no additional constraints.