문자 연금술

아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제

민겸이는 연금술을 배우는 견습 연금술사이다. 졸업 시험을 앞둔 민겸이는 NN개의 aMM개의 b를 전부 이용하여 가장 가치가 높은 문자열을 만들고 싶다. 문자열의 가치는 다음과 같이 측정한다.

  1. 어떤 문자열에 대해서 k=1,2,3,k = 1, 2, 3, \cdots에 대해 2를 반복한다.
  2. 해당 문자열에서 거리가 kk인 동일한 종류의 문자 쌍이 존재할 경우 가치가 kk만큼 증가한다. 이때, 거리가 kk인 문자 쌍이 여러 개여도 가치는 kk만큼만 증가한다.
  3. ii번째 문자와 jj번째 문자 사이의 거리는 ij|i-j|이다. 예를 들어, 문자열 abba에서 두 a 사이의 거리는 33이고, 두 b 사이의 거리는 11이다.

가치가 88인 문자열 aabba를 예로 들어 보자.

  1. k=1k = 1일 때 (1,2)(1, 2), (3,4)(3, 4) 등의 문자 쌍이 있으므로 가치가 11 증가한다.
  2. k=2k = 2일 때는 거리가 22인 문자 쌍이 없으므로 가치를 증가시킬 수 없다.
  3. k=3k = 3일 때 (2,5)(2, 5) 등의 문자 쌍이 있으므로 가치가 33 증가한다.
  4. k=4k = 4일 때 (1,5)(1, 5) 등의 문자 쌍이 있으므로 가치가 44 증가한다.
  5. k5k \ge 5일 때는 거리가 kk인 문자 쌍이 없으므로 가치를 증가시킬 수 없다.
  6. 총 가치는 1+3+4=81 + 3 + 4 = 8이다.

NN개의 aMM개의 b를 전부 이용하여 만들 수 있는 문자열의 최대 가치를 구하고, 해당 가치를 가지는 문자열을 하나 출력하는 프로그램을 작성하여라.

입력

입력의 첫 번째 줄에 a의 개수 NNb의 개수 MM이 공백으로 구분되어 주어진다. (1N10,000;(1 \le N \le 10\\,000; 1M10,000)1 \le M \le 10\\,000)

출력

첫 번째 줄에 주어진 알파벳 소문자들로 만들 수 있는 최대 가치를 출력한다.

두 번째 줄에 해당 가치를 가지는 문자열을 출력한다. 답이 여러 개라면, 하나만 출력한다.