Minimizing Notification Times

There are n students who are waiting for a consultation with their teacher. Each student i has estimated the time they need for three parts of the consultation process:

• Entry process: takes \( s_i \) milliseconds.
• Question answering: takes \( a_i \) milliseconds.
• After the answer, the student immediately sends a message to the class group (this takes negligible time).
• Exit process: takes \( e_i \) milliseconds. Note that \( e_i \) is usually one of \( \{10000, 20000, 30000\} \).

The teacher can arrange the order in which the students enter the office. Once one student leaves, the next student immediately starts his/her process.

The timeline for a student \( i \) in the consultation when scheduled in a given order is as follows:

1. The student starts at time \( T \) and spends \( s_i \) milliseconds to enter.
2. The teacher then spends \( a_i \) milliseconds to answer the student's question.
3. Immediately after the answer, the student sends a message. The time at which the message is sent for student \( i \) is \( T + s_i + a_i \).
4. The student then packs up and exits, taking \( e_i \) additional milliseconds.

The objective is to determine an ordering of the students to minimize the sum of all the message sending times.

Observation: If the teachers process the students in a particular order \( p[1], p[2], \dots, p[n] \), let the cumulative time before student \( p[k] \) be \( C_k = \sum_{j=1}^{k-1} (s_{p[j]} + a_{p[j]} + e_{p[j]}) \). Then, student \( p[k] \) sends the message at time \( C_k + s_{p[k]} + a_{p[k]} \). The total message time is:

\[ \text{Total} = \sum_{k=1}^{n} \Bigl(C_k + s_{p[k]} + a_{p[k]}\Bigr) = \text{constant} + \sum_{k=1}^{n} (n-k) \cdot (s_{p[k]} + a_{p[k]} + e_{p[k]}), \]

Thus, to minimize the sum, one should order the students in ascending order of \( s_i+a_i+e_i \). Your task is to compute the minimum total message time using the best order.

inputFormat

The input consists of the following:

1. The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of students.
2. Each of the following n lines contains three integers: \( s_i \), \( a_i \), and \( e_i \) where \( e_i \) is one of {10000, 20000, 30000}.

outputFormat

Output a single integer, which is the minimum possible sum of the times at which all students send their messages to the group.

sample

1
100 200 10000

300