Problem Description

There are $n$ students who come to the teacher for Q&A at the same time. Each student has estimated in advance the time needed for their own Q&A. The teacher can decide the order of Q&A, and students enter the teacher’s office one by one for Q&A.

The Q&A process for one student is as follows:

1. First, the student enters the office. Student $i$ needs $s_{i}$ milliseconds.

2. Then the student asks questions and the teacher answers. Student $i$ needs $a_{i}$ milliseconds.

3. After the Q&A is finished, the student is very happy and sends a message in the course chat group. The time needed for this can be ignored.

4. Finally, the student packs up and leaves the office, which takes $e_{i}$ milliseconds. Usually it takes $10$ seconds, $20$ seconds, or $30$ seconds, i.e. $e_{i}$ can be $10000$, $20000$, or $30000$.

After one student leaves the office, the next student can immediately enter.

The Q&A starts at time $0$. The teacher wants to arrange the Q&A order reasonably so that the sum of the times when students send messages in the course chat group is minimized.

Input Format

The first line contains an integer $n$, representing the number of students.

The next $n$ lines describe the time for each student. The $i$-th line contains three integers $s_{i}, a_{i}, e_{i}$, with the meanings described above.

Output Format

Output one integer, representing the minimum possible sum of the times when students send messages in the course chat group.

3
10000 10000 10000
20000 50000 20000
30000 20000 30000

280000

Hint

Sample Explanation

If the Q&A order is $1,3,2$, then the message sending times are $20000,80000,180000$.

Constraints and Notes

For $30\%$ of the testdata, $1 \leq n \leq 20$.

For $60\%$ of the testdata, $1 \leq n \leq 200$.

For all testdata, $1 \leq n \leq 1000$, $1 \leq s_{i} \leq 60000$, $1 \leq a_{i} \leq 1000000$, $e_{i} \in\{10000,20000,30000\}$, i.e. $e_{i}$ must be one of $10000$, $20000$, or $30000$.

Lanqiao Cup 2020 National Finals, Group A Problem H (Group B Problem H, Group C Problem J).

Translated by ChatGPT 5