시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 40 3 3 7.500%

문제

데이브 존슨은 책 수집가이다. 오랜 세월이 지난 후 그는 너무 많은 책들을 모아서 새 책장을 사기로 결심했다. 그는 품질이 모두 다른 여러개의 책장을 샀는데, 문제는 그가 가장 좋아하는 책들을 가장 좋은 책장의 맨 위에 놓고 싶었다는 것이다. 이 책장의 한 칸은 최대 10개의 책을 넣을 수 있다.

그러나 괴짜인 데이브는 가장 좋아하는 책들을 정렬하는 특별한 방법이 있다. 그 책들은 당연히 알파벳 순서로 정렬되어 있어야 하지만, 또한 같은 알파벳이 제목의 같은 위치에 있는 책은 붙어 있으면 안된다는 것이 문제. 또 중요한 것은 데이브는 오직 알파벳 문자만 문자로 치고, 띄어쓰기나 쉼표, `등은 문자로 치지 않는다는 것이다. 그러므로 "Portnoy's Complaint"라는 제목에서 's'는 8번째 문자이고, 'c'는 9번째 문자이다. 문제에 대한 예를 들자면 "The Grapes Of Wrath" 라는 제목의 책과 "One Flew Over The Cuckoo's Nest" 라는 제목의 책은 서로 붙어 있을 수 없는데, 그것은 두 제목의 세번째 문자가 공통적으로 'e'이기 때문이다.

이 문제를 해결하려는 우리들을 도와주기 위해서(혹은 문제를 더 어렵게 만들기 위해서), 데이브는 '선호도 지수'라는 것을 모든 책들에 부여했다. 주어지는 책들과 선호도 지수의 목록을 활용해 데이브에게 그가 책장의 가장 윗 칸에 놓게 되는 책들의 목록을 알려 주자. 맨 윗 칸에 놓인 책들의 선호도 지수의 합이 가장 크게 만들어야 한다.

입력

입력 파일마다 한 개의 테스트 케이스가 있다. 입력의 첫줄에는 데이브의 책장 맨 윗칸 후보에 올라있는 책들의 개수 N(10<=N<=2500)이, 그 뒤의 N개의 줄은 각각 책의 선호도 지수 E와 책의 제목 S가 한 칸의 띄어쓰기로 구별되어 입력되고, E는 200 이하의 정수이며 S는 문자열이며 30문자를 넘지 않는다. S에는 적어도 하나의 알파벳 문자가 포함되어 있다. 입력은 stdin 형식이다.

출력

출력의 첫째 줄은 데이브의 맨 윗칸에 놓을 책의 개수인 정수 M을 출력해야 하며, 두번째 줄은 맨 윗 칸의 모든 책들의 선호도 지수의 합이어야 하고, 다음 M개의 줄은 맨 윗 칸에 놓을 책들의 제목이 사전식 순서로 정렬되어 출력되어야 한다. 한 개보다 많은 정답이 존재할 경우 아무 것이나 출력해도 상관 없다. 출력은 stdout 형식이어야 한다.

예제 입력

12
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

예제 출력

8
969
For Whom The Bell Tolls
Great Expectations
Hamlet
L'Etranger
Of Mice And Men
The Grapes Of Wrath
Ulysses
War And Peace

힌트