시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 19 1 1 100.000%

문제

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

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

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

입력

첫째 줄에 단어의 개수 N과 새로운 단어의 길이 M이 주어진다. N은 100보다 작거나 같다. M은 2000보다 작거나 같다. 둘째 줄부터 단어가 들어온다. 단어는 알파벳으로만 이루어져 있다.

출력

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

예제 입력

5 32
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 Alpha__Beta__Gamma_Delta_Epsilon

출처