밑줄 넣기

세준이는 주어진 N개의 영어 단어를 순서대로 이어 붙여 길이가 M인 새 단어를 만들려고 한다. 인접한 두 단어 사이에는 반드시 하나 이상의 _를 넣어야 한다.

새 단어의 길이가 M이 될 때까지 _를 더 넣을 수 있지만, _는 단어와 단어 사이에만 넣을 수 있다. 따라서 새 단어는 _로 시작하거나 끝날 수 없다.

단어 사이에 들어가는 _의 개수는 가능한 한 모두 같아야 한다. 모두 같게 만들 수 없다면, 단어 사이의 _ 개수 중 최댓값과 최솟값의 차이가 정확히 1이 되도록 해야 한다.

조건을 만족하는 새 단어 중 사전 순으로 가장 앞서는 단어를 출력하라.

첫째 줄에 단어의 개수 N과 만들어야 하는 단어의 길이 M이 주어진다. 둘째 줄부터 N개의 줄에 영어 단어가 한 줄에 하나씩 주어진다.

조건을 만족하는 새 단어 중 사전 순으로 가장 앞서는 단어를 한 줄에 출력한다.

문자의 사전 순서는 다음과 같다.

'A' < 'B' < 'C' < ... < 'Z' < '_' < 'a' < 'b' < 'c' < ... < 'z'

• 2 <= N <= 10
• 3 <= M <= 200
• 각 단어는 알파벳 대문자와 소문자로만 이루어져 있다.
• 각 단어의 길이는 1 이상 10 이하이다.
• N개 단어 길이의 합을 len이라고 할 때, len + N - 1 <= M을 만족한다.