Top Shelf of the Bookshelf
Time limit2sMemory limit128 MB
Pick up to 10 book titles, sorted lexicographically, so that no two neighboring titles share the same letter at any aligned alphabetic position, maximizing total preference score.
- Level
Medium7 of 10
- Topics
- Dynamic programming, String, Sorting, Implementation
- Solved
- No attempts yet
Problem
Dave Johnson collects books. After many years, he has gathered so many books that he bought several bookshelves of different quality. Dave wants to place his favorite books on the top shelf of the best bookshelf. That shelf can hold at most 10 books.
His ordering rule is strict. The books must be placed in lexicographic order by title. Also, for every two neighboring books in that order, after keeping only alphabetic characters from each title, there must be no position where the two titles have the same alphabetic character. Spaces, commas, quotation marks, and similar characters are ignored when positions are counted. In "Portnoy's Complaint", s is the 8th alphabetic character and c is the 9th. Therefore, "The Grapes Of Wrath" and "One Flew Over The Cuckoo's Nest" cannot be neighbors, because their third alphabetic characters are both e.
Each book also has a preference score. Choose the books to place on the top shelf so that the sum of the selected preference scores is as large as possible.
Input
The input contains one test case.
The first line contains the number N of candidate books. (10 ≤ N ≤ 2500)
Each of the next N lines contains a preference score E and a book title S, separated by one space. E is a positive integer not greater than 200. S is a string of length at most 30 and contains at least one alphabetic character.
Output
On the first line, print the number M of selected books.
On the second line, print the sum of the preference scores of the selected books.
On each of the next M lines, print one selected title, in lexicographic order.
If more than one optimal answer exists, you may print any one of them.