import java.util.Arrays;
import java.util.Scanner;

// Job class to hold information about each job.
class Job {
    int id;       // Job ID
    int profit;   // Profit of the job
    int deadline; // Deadline of the job
    
    // Constructor to initialize job details
    public Job(int id, int profit, int deadline) {
        this.id = id;
        this.profit = profit;
        this.deadline = deadline;
    }
}

// Comparator to sort jobs based on profit in descending order
class JobComparator implements java.util.Comparator<Job> {
    @Override
    public int compare(Job job1, Job job2) {
        return job2.profit - job1.profit; // Sorting in descending order of profit
    }
}

public class Main {

    // Function to perform Job Sequencing with Deadlines
    public static void jobSequencing(Job[] jobs, int n) {
        // Sort the jobs based on profit in descending order
        Arrays.sort(jobs, new JobComparator());
        
        // Find the maximum deadline to determine the size of the result array
        int maxDeadline = 0;
        for (int i = 0; i < n; i++) {
            if (jobs[i].deadline > maxDeadline) {
                maxDeadline = jobs[i].deadline;
            }
        }
        
        // Array to store the result (sequenced jobs)
        int[] result = new int[maxDeadline];
        
        // Initialize all slots as empty (-1 means no job is scheduled)
        Arrays.fill(result, -1);
        
        // Variable to track total profit
        int totalProfit = 0;
        
        // Iterate over all jobs
        for (int i = 0; i < n; i++) {
            // Find a free slot for the job (starting from the latest available slot)
            for (int j = jobs[i].deadline - 1; j >= 0; j--) {
                if (result[j] == -1) { // If the slot is free
                    result[j] = jobs[i].id; // Schedule the job
                    totalProfit += jobs[i].profit; // Add profit
                    break;
                }
            }
        }
        
        // Print the scheduled jobs and total profit
        System.out.println("Jobs scheduled in the sequence are:");
        for (int i = 0; i < maxDeadline; i++) {
            if (result[i] != -1) {
                System.out.print("Job " + result[i] + " ");
            }
        }
        System.out.println();
        System.out.println("Total Profit = " + totalProfit);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Take input for number of jobs
        System.out.print("Enter number of jobs: ");
        int n = scanner.nextInt();

        // Create an array of jobs
        Job[] jobs = new Job[n];

        // Take input for jobs (id, profit, deadline)
        System.out.println("Enter job details (ID Profit Deadline):");
        for (int i = 0; i < n; i++) {
            System.out.print("Job " + (i + 1) + ": ");
            int id = scanner.nextInt();
            int profit = scanner.nextInt();
            int deadline = scanner.nextInt();
            jobs[i] = new Job(id, profit, deadline);
        }

        // Call the job sequencing function
        jobSequencing(jobs, n);

        scanner.close();
    }
}