P8732 [Lanqiao Cup 2020 National ABC] Q&A

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.

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 one integer, representing the minimum possible sum of the times when students send messages in the course chat group.

**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