Freelancer

Time Limit: 3 sec

 

The Problem

As a freelancer I apply for job in various freelance websites like Upwork, Toptal

Freelancer, Peopleperhour, GetACoder etc. Sometimes I get multiple projects offer at the same time. Please help me to choose or accept offers so I can make highest revenue.

 

In this problem, you are given a list of project description where every project has a deadline and associated revenue if the project is finished before the deadline. It is also given that every project takes single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one project can be scheduled at a time.

 

The Input

At the first line of each test case will be the number of projects offer, N. Then in the next N lines contains project description. Each line of project description contains P D R, Where P is the project name, D is the deadline and R is revenue.

1 <= N <= 26

‘A’ <= P <= ‘Z’

1 <= D <= 100

1 <= R <= 1000

 

The Output

For each test case print two lines of output. At first line print the highest revenue and in second line print all the  project's name in alphabetical order accepted to make highest revenue. All projects name must be separated by a blank space.

 

Sample Input

2

Z 1 100

A 1 50

3

A 2 20

B 2 100

C 1 60

 

Sample Output

100

Z

160

B C

 

 

 

[University Level]

Inter School & College Programming Contest (ISCPC) 2017

Problem Setter: Md. Helal Uddin