Problem Description

There are n students seeking consultation from a teacher simultaneously. Each student has estimated their consultation time requirements. The teacher can arrange the consultation order, with students entering the teacher's office sequentially.

The consultation process for each student consists of:

1. Entering the office - studant i requires si milliseconds
2. Asking questions and receiving answers - student i requires ai milliseconds
3. Posting a message in the course group after consultation (time negligible)
4. Packing up and leaving the office - student i requires ei milliseconds, wich is typically 10000, 20000, or 30000 ms

When one student leaves the office, the next student can immediately enter. The consultation starts at time 0. The teacher needs to arrange the consultation sequence to minimize the sum of message posting times in the course group.

Input Format

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

The next n lines each contain three integers si, ai, ei describing each student's time requirements.

Output Format

Output a single integer representing the minimum possible sum of message posting times.

Example

Input

3
10000 10000 10000
20000 50000 20000
30000 20000 30000

Output

280000

Explanation

Using sequence 1, 3, 2, the message posting time are 20000, 80000, and 180000 respectively.

Constraints

• 30% of test cases: 1 ≤ n ≤ 20
• 60% of test cases: 1 ≤ n ≤ 200
• 100% of test cases: 1 ≤ n ≤ 1000, 1 ≤ si ≤ 60000, 1 ≤ ai ≤ 1000000, ei ∈ {10000, 20000, 30000}

Solution Approach

The optimal strategy involves sorting students by their total consultation time (si + ai + ei) in ascending order. This greedy approach minimizes the cumulative waiting time.

Implementation

#include<iostream>
#include<algorithm>
using namespace std;

struct Consultation {
    int entry_time;
    int question_time;
    int exit_time;
    int total_time;
};

bool compareStudents(const Consultation &x, const Consultation &y) {
    return x.total_time < y.total_time;
}

int main() {
    int student_count;
    cin >> student_count;
    
    Consultation students[1001];
    long long completion_times[1001] = {0};
    long long result = 0;
    
    for(int i = 0; i < student_count; i++) {
        cin >> students[i].entry_time >> students[i].question_time >> students[i].exit_time;
        students[i].total_time = students[i].entry_time + students[i].question_time + students[i].exit_time;
    }
    
    sort(students, students + student_count, compareStudents);
    
    for(int i = 0; i < student_count; i++) {
        if(i == 0) {
            completion_times[i] = students[i].entry_time + students[i].question_time;
        } else {
            completion_times[i] = completion_times[i-1] + students[i-1].exit_time + 
                                students[i].entry_time + students[i].question_time;
        }
        result += completion_times[i];
    }
    
    cout << result;
    return 0;
}