import java.util.*;


public class JobSequencing {

    private static void calculateMaxProfit(Job[] ar,int md) {
        
        Arrays.sort(ar,(Job a,Job b)->{
           return  b.profit-a.profit;
        });
        int profit=0;
        for(Job j:ar){
            System.out.println(j.deadline+";"+j.profit+";"+j.id);
        }
        System.out.println();
        char js[]=new char[md];
        boolean []slot=new boolean[md];
        for(int i=0;i<ar.length;i++){
            for(int j=Math.min(md-1,ar[i].deadline-1);j>=0;j--){
                if(slot[j]==false){
                    slot[j]=true;
                    profit+=ar[i].profit;
                    js[j]=ar[i].id;
                    break;
                }
            }
        }

        System.out.println("max profit is :"+profit);
        System.out.println("job sequence");
        for(char c:js){
            System.out.print(c+" ");;
        }



    }



    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        System.out.println("enter no of jobs:");
        int n=sc.nextInt();
        Job [] ar=new Job[n];
        char c='a';
        int md=0;
        for(int i=0;i<n;i++){
            System.out.println("enter deadline for job :"+(i+1));;
            int d=sc.nextInt();
            md=Math.max(d,md);
            System.out.println("enter profit for job :"+(i+1));;
            int p=sc.nextInt();
            Job j=new Job(c, d, p);
            c=(char)(c+1);
            ar[i]=j;
        }
        calculateMaxProfit(ar,md);
        
        
            }
        
          
}
public class Job {
    char id;
    int deadline;
    int profit;
    public Job(char id, int deadline, int profit) {
        this.id = id;
        this.deadline = deadline;
        this.profit = profit;
    }
    



}