책장 맨 위 칸

데이브 존슨은 책 수집가이다. 오랜 시간 동안 책이 많아지자, 그는 품질이 서로 다른 여러 책장을 샀다. 데이브는 자신이 가장 좋아하는 책들을 가장 좋은 책장의 맨 위 칸에 놓으려고 한다. 그 칸에는 책을 최대 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을 넘지 않는 문자열이며 적어도 하나의 알파벳 문자를 포함한다.

첫째 줄에 선택한 책의 개수 M을 출력한다. 둘째 줄에 선택한 책들의 선호도 지수 합을 출력한다. 다음 M개의 줄에는 선택한 책들의 제목을 사전식 순서대로 한 줄에 하나씩 출력한다.

최적해가 여러 개라면 그중 아무 것이나 출력해도 된다.