만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

K번째 문장

시간 제한3초메모리 제한512 MB

요약
서로 다른 단어 n개로 이어 붙여 만든 길이 m의 문장 중 사전순으로 K번째 문장을 출력합니다. 그런 문장이 없으면 하이픈(-)을 출력합니다.
난이도

보통10점 중 7점

유형
동적 계획법, 트라이, 문자열
정답자
아직 제출이 없습니다

문제

Kita_masa라는 학생이 영어 시험을 보고 있다. 이 시험에서는 길이가 mm인 문장을 하나 써야 한다.

그는 영문법을 완전히 잊어버렸다. 그래서 자신이 아는 단어들을 이어 붙여 만들 수 있는 길이 mm의 문장을 모두 고려하기로 했다. 후보들을 사전순으로 정렬해 KK번째 문장을 쓰기로 했다. 오늘의 행운의 숫자가 KK이므로 이것이 올바른 문장이라고 믿는다.

각 단어는 여러 번 써도 되고, 전혀 쓰지 않아도 된다. 단어 사이에는 다른 문자가 들어가지 않는다. 단어를 나열한 순서가 다르면 이어 붙인 문자열이 같더라도 서로 다른 문장으로 본다.

입력

첫째 줄에 세 정수 nn, mm, KK (1≤n≤1001 \leq n \leq 100, 1≤m≤20001 \leq m \leq 2000, 1≤K≤10181 \leq K \leq 10^{18})가 공백으로 구분되어 주어진다. 이어서 nn개의 줄에 Kita_masa가 아는 단어가 한 줄에 하나씩 주어진다. 각 단어의 길이는 1 이상 200 이하이며, 소문자 알파벳으로만 이루어져 있다. 주어지는 단어는 모두 서로 다르다.

출력

사전순으로 KK번째 (1부터 시작) 길이 mm의 문장을 출력한다. 그런 문장이 없으면 "-"를 출력한다.

예제3

  1. 예제 1

    입력
    2 10 2
    hello
    world
    
    예상 출력
    helloworld
    
  2. 예제 2

    입력
    3 3 6
    a
    aa
    b
    
    예상 출력
    aba
    
  3. 예제 3

    입력
    2 59 1000000000000000000
    a
    b
    
    예상 출력
    -