Top Shelf of the Bookshelf

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.

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.

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.