#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct Jobs {
	 int id;
	 int deadline;
	 int profit;
} Jobs;
int compare(const void* a, const void* b){
	 Jobs* temp1 = (Jobs*)a;
	 Jobs* temp2 = (Jobs*)b;
	 return (temp2->profit - temp1->profit);
}
void main(){
	 Jobs arr[10];
	 int maxdeadline,n,maxProfit=0,i,j,slot[10];
	 clrscr();
	 printf("Enter total number of jobs\n");
	 scanf("%d",&n);
	 printf("Enter all jobs as ( deadline, profit)\n");
	 for(i=0;i<n;i++){
		scanf("%d%d",&arr[i].deadline,&arr[i].profit);
		slot[i] = 0;
		arr[i].id=i+1;
	 }
	 printf("Enter the deadline\n");
	 scanf("%d",&maxdeadline);
	 printf("Following is maximum profit sequence of Jobs: \n");
	 qsort(arr, n, sizeof(Jobs), compare);
	 for (i = 0; i < n; i++) {
			if(arr[i].deadline <= maxdeadline){
				slot[i]=1;
				maxdeadline-=arr[i].deadline;
			}
	 }
	 for (i = 0; i < n; i++)
			if (slot[i]){
				 printf("Job %d with deadline %d and profit %d\n", arr[i].id,arr[i].deadline,arr[i].profit);
				 maxProfit+=arr[i].profit;
			}
	printf("Maximum profit for the given job sequence is : %d",maxProfit);
	getch();
}