It’s 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, with the \(i\)th friend initially
at position \(P_i\) metres along it.
The \(i\)th friend is able to walk in
either direction along the field at a rate of one metre per \(W_i\) seconds, and their hearing is good
enough to be able to hear music up to and including \(D_i\) metres away from their position.
Multiple students may occupy the same positions on the field, both
initially and after walking.

You’re going to hold a little 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 will walk
along the field for the minimum amount of time such that they end up
being able to hear your concert (in other words, such that each friend
\(i\) ends up within \(D_i\) units of \(c\)).

You’d like to choose \(c\) such that
you minimize the sum of all \(N\) of
your friends’ walking times. What is this minimum sum (in seconds)?
Please note that the result might not fit within a 32-bit integer.

\((1 \le i \le N)\)

Marks

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

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)\).

Output one integer which is the minimum possible sum of walking times
(in seconds) for all \(N\) of your
friends to be able to hear your concert.

생성자가 기록되지 않았습니다.

출처 CCC 2021 Senior