시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 119 30 16 26.230%

문제

세준이는 N개의 영어 단어를 가지고 있다. 세준이는 N개의 영어단어를 서로 합쳐서 새로운 단어를 만들려고 한다. 새로운 단어을 만드는 방법은 다음과 같다.

  • N개의 영어 단어의 사이에는 적어도 한 개의 _이 있어야 한다.
  • N개의 영어 단어를 합쳐서 새롭게 만든 단어의 길이는 M이다.
  • 입력으로 주어진 단어의 순서를 변경할 수 없다.
  • 각 단어 사이에 놓일 밑줄의 개수는 가능한 한 최대한 공평하게 분배되어야 한다.

N과 M이 주어지고, 영어 단어가 주어졌을 때, 세준이가 새롭게 만든 영어 단어 중에서 사전순으로 가장 앞서는 것을 출력하는 프로그램을 작성하시오.

이 문제에서 알파벳의 순서는 'A' < 'B' < ... < 'Z' < '_' < 'a' < 'b' < ... < 'z' 이다.

입력

첫째 줄에 단어의 개수 N과 새로운 단어의 길이 M이 주어진다. N은 100보다 작거나 같다. 모든 단어 길이의 합을 len이라고 했을 때, M은 N+len-1보다 크거나 같고, 200보다 작거나 같다. 둘째 줄부터 단어가 들어온다. 단어는 알파벳으로만 이루어져 있고, 길이는 10을 넘지 않는다.

출력

첫째 줄에 정답을 출력한다.

예제 입력 1

5 32
Alpha
Beta
Gamma
Delta
Epsilon

예제 출력 1

Alpha_Beta_Gamma__Delta__Epsilon

힌트

Alpha_Beta_Gamma__Delta__Epsilon
Alpha_Beta__Gamma_Delta__Epsilon
Alpha_Beta__Gamma__Delta_Epsilon
Alpha__Beta_Gamma_Delta__Epsilon
Alpha__Beta_Gamma__Delta_Epsilon
Alpha__Beta__Gamma_Delta_Epsilon

출처