Lunch Concert

Time limit1sMemory limit1024 MB

Summary

Choose an integer concert position on a line to minimize the total time for N friends to walk within hearing range of it.

Level: Medium7 of 10
Topics: Math, Sorting, Greedy, Prefix sum
Solved: No attempts yet

Problem

It is lunchtime at your school! Your N friends are all standing on a long field, as they usually do. The field can be represented as a number line, and the ith friend starts at position $P_i$ metres along it. The ith friend can walk in either direction along the field at a rate of one metre per $W_i$ seconds, and has hearing good enough to hear music up to and including $D_i$ metres away from their position. Multiple students may occupy the same position on the field, both initially and after walking.

You are going to hold a small concert at some position $c$ metres along the field, where c is any integer of your choice, and text all of your friends about it. Once you do, each of them walks for the minimum amount of time such that they can hear your concert. In other words, each friend i ends up within $D_i$ units of $c$ .

You want to choose $c$ to minimize the sum of the walking times of all N friends. What is this minimum sum in seconds? Note that the result might not fit in a 32-bit integer.

Input

The first line of input contains N.

The next N lines contain three space-separated integers, $P_i$ , $W_i$ , and $D_i$ ( $1 \le i \le N$ ).

The following table shows how the available 15 marks are distributed.

Output

Output one integer, the minimum possible sum of walking times in seconds for all N of your friends to be able to hear your concert.

Constraints

$1 \le N \le 200\,000$
$0 \le P_i \le 1\,000\,000\,000$
$1 \le W_i \le 1000$
$0 \le D_i \le 1\,000\,000\,000$

Examples3

Example 1
Input
```
1
0 1000 0
```
Expected output
```
0
```
Example 2
Input
```
2
10 4 3
20 4 2
```
Expected output
```
20
```
Example 3
Input
```
3
6 8 3
1 4 1
14 5 2
```
Expected output
```
43
```