아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

이번에는 C번이 문자열

시간 제한1초메모리 제한1024 MB

요약
길이가 같은 N개의 문자열 중 K개를 골라 이어 붙인 뒤 문자를 재배치해 만들 수 있는 문자열 가운데 사전순으로 가장 앞선 것을 출력한다.
난이도

보통10점 중 5점

유형
정렬, 그리디, 문자열
정답자
아직 제출이 없습니다

문제

지난 대회에 이어 이번에도 문자열 문제를 출제하고 싶은 에릭은 다음과 같은 문제를 떠올렸다. 정답 코드를 짜기 귀찮은 에릭을 위해 대신 문제를 풀어주자!

  • 길이가 MM인 NN개의 문자열 S_1,S_2,⋯ ,S_NS\_1, S\_2, \cdots, S\_N이 주어진다.

  • 다음 방법으로 만들 수 있는 문자열 TT 중 사전순으로 가장 앞에 오는 것을 출력한다.

    1. S_1,S_2,⋯ ,S_NS\_1, S\_2, \cdots, S\_N 중 KK개를 선택한 후, 이어 붙여서 길이 K⋅MK \cdot M의 문자열을 만든다.
    2. 이렇게 얻은 K⋅MK \cdot M개의 문자를 적당히 재배치하여 문자열 TT를 만든다.

서로 다른 두 문자열 aa, bb에 대해 다음 중 하나가 성립할 때 문자열 aa가 문자열 bb보다 사전순으로 앞에 온다고 말한다.

  • aa가 bb의 접두사
  • aa와 bb가 달라지는 첫 위치에서 aa의 문자가 알파벳 순으로 bb의 문자보다 앞에 위치함

입력

첫 번째 줄에 세 정수 NN, MM, KK가 공백으로 구분되어 주어진다.

i+1i + 1번째 줄에는 문자열 S_iS\_i가 주어진다. (1≤i≤N)(1 \le i \le N)

출력

S_1,S_2,⋯ ,S_NS\_1, S\_2, \cdots, S\_N을 이용하여 위에서 설명한 방법으로 만들 수 있는 문자열 TT 중 사전순으로 가장 앞에 오는 것을 출력한다.

제한

  • 1≤K≤N≤3001 \le K \le N \le 300
  • 1≤M≤3001 \le M \le 300
  • S_iS\_i는 영어 대문자로 구성된 길이 MM의 문자열 (1≤i≤N)(1 \le i \le N)

예제2

  1. 예제 1

    입력
    4 1 2
    Y
    Y
    Z
    X
    
    예상 출력
    XY
    
  2. 예제 2

    입력
    3 4 2
    ABCD
    AACC
    ABCC
    
    예상 출력
    AAABCCCC