세 분류 할인전

문제

온라인 쇼핑몰에서 다음 할인전에 사용할 상품 분류를 정하고 있다. 쇼핑몰의 상품 분류는 알파벳 대문자 A부터 차례대로 K개이며, 각 상품은 정확히 하나의 분류에 속한다. 운영자는 최근 접수된 N건의 구매 요청을 접수 순서대로 기록했다. 기록의 각 문자는 해당 요청에 담긴 상품의 분류를 나타낸다. 같은 분류의 요청이 여러 번 등장하면 각각 별개의 요청으로 센다. 할인전에는 서로 다른 분류를 정확히 세 개 골라야 한다. 분류를 하나 선택할 때마다 그 분류에 정해진 준비 비용을 한 번 지불한다. 선택한 분류에 구매 요청이 몇 건 있었는지는 준비 비용에 영향을 주지 않는다. 세 분류의 준비 비용 합은 주어진 예산 B 이하여야 한다. 구매 요청 기록에 한 번도 등장하지 않은 분류도 선택할 수 있으며, 이때에도 준비 비용은 그대로 지불한다. 선택한 세 분류 중 하나에 속하는 구매 요청은 할인전의 안내 대상으로 정한다. 운영자는 안내 대상인 요청의 수가 최대가 되도록 분류를 선택하려 한다. 예를 들어 한 분류의 요청이 네 번 등장하고 그 분류를 선택했다면, 그 네 요청을 모두 안내 대상으로 센다. 한 요청을 두 번 세는 일은 없다. 기록에서 요청이 나타난 위치나 서로 이웃하는지는 선택 결과에 영향을 주지 않는다. 안내 대상 요청 수가 같은 선택이 여러 개라면 준비 비용 합이 가장 작은 선택을 택한다. 요청 수와 준비 비용 합까지 같다면, 선택한 세 분류의 문자를 알파벳 오름차순으로 붙인 문자열이 사전순으로 가장 앞서는 선택을 택한다. 길이가 같은 두 문자열의 사전순은 처음으로 다른 위치의 문자를 비교하여 정한다. 예산 안에서 서로 다른 세 분류를 선택할 수 없다면 할인전을 열 수 없다. 운영자가 선택할 세 분류와 그 선택의 안내 대상 요청 수, 준비 비용 합을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, K, B가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, 1 ≤ K ≤ 26, 0 ≤ B ≤ 3,000,000,000이다.
둘째 줄에 구매 요청 기록을 나타내는 길이 N의 문자열 S가 주어진다. S의 각 문자는 A부터 K번째 알파벳 대문자까지 중 하나이다.
셋째 줄에 각 분류의 준비 비용을 나타내는 정수 C_1, C_2, …, C_K가 공백으로 구분되어 주어진다. C_i는 i번째 알파벳 분류의 준비 비용이며, 1 ≤ C_i ≤ 1,000,000,000이다.

출력

예산 안에서 서로 다른 세 분류를 선택할 수 없다면 첫째 줄에 -1을 출력한다. 선택할 수 있다면 첫째 줄에 선택한 세 분류의 문자를 알파벳 오름차순으로 붙인 길이 3의 문자열을 출력한다. 둘째 줄에 안내 대상 요청 수와 준비 비용 합을 공백으로 구분하여 정수로 출력한다. 선택은 지문에 명시된 우선순위를 따라야 한다.

10 5 8
ABACEDABAA
5 4 2 3 1

ACE
7 8

8 4 6
ABCDABCD
4 1 1 1

BCD
6 3

5 3 8
AACAA
2 3 4

-1

출처: Devin.KR 자체 제작