Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
The Top Shelf
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1499Accepted: 419Special Judge


Dave Johnson is a book collector. Over the years, he collected so many books that he decided he needed to buy some new bookcases. He bought enough cases, of different quality, to fit all of his books. One problem remained, however. He wanted to put his favorite books in a special display on the top shelf of his best bookcase. This shelf is wide enough to fit at most 10 books.

This would normally be an easy task, but Dave is particular about the way he displays his favorite books. Not only must they be sorted alphabetically by title, but also there must never be two books next to each other that have the same letter in the same position in the title. Note that Dave looks only at alphabetical characters in the titles of his books, skipping spaces, apostrophes, etc., and he ignores the case of the letters. Thus, in the title "Portnoy's Complaint", 's' is the 8th character, and 'c' is the 9th character. As an example, "The Grapes Of Wrath" and "One Flew Over The Cuckoo's Nest" cannot be next to each other since the third letter of each title is the letter 'e'.

In order to help make this decision, Dave has assigned an emotional value to each of his books. Given a list of titles and the emotional value of each book, your job is to help Dave decide which books should go on his top shelf so as to maximize the total emotional value of all of the books.


There will be one test case in each input file. The first line will contain an integer N (10 <= N <= 2500), specifying the number of books that are candidates for Dave's top shelf. The next N lines will each contain an integer E and a string S, separated by a single space. E is an integer no larger than 200 that represents the emotional value for Dave of the book with title S. Note that S can have an arbitrary number of spaces, but will not exceed 30 characters. S is guaranteed to contain at least one alphabetical character. Input should be read from stdin.


The first line of the output should contain an integer M giving the number of books on Dave's top shelf. The second line should give the total emotional value of all of the books on the shelf. The next M lines should give the titles of the books on the shelf, in lexicographic order. If there is more than one solution, any one will do. Output should be written to stdout.

Sample Input

117 The Pearl
42 L'Etranger
135 Hamlet
100 War And Peace
55 The Prince
175 Of Mice And Men
200 The Grapes Of Wrath
120 Ulysses
87 For Whom The Bell Tolls
10 Oliver Twist
50 Snow Crash
110 Great Expectations

Sample Output

For Whom The Bell Tolls
Great Expectations
Of Mice And Men
The Grapes Of Wrath
War And Peace


[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator