인쇄물

Pelle는 컴퓨터에 있는 글을 이제 편집하여 인쇄하려고 한다. 그는 인쇄물에 ``고정 폭'' 글꼴을 사용하려고 한다. 즉, 모든 문자의 너비가 같다(한 줄에서 같은 양의 공간을 차지한다). 또한 인쇄물의 각 줄을 최대 $n$자의 주어진 줄 길이에 맞추려고 한다.

그는 두 단어 사이에 정확히 하나의 공백이 있어야 하므로 모든 줄에 정확히 $n$자가 들어가게 하는 것은 거의 불가능하다는 것을 깨닫는다. 하지만 인쇄물의 형식을 원하는 결과에 최대한 가깝게 만들 수 있다면 만족한다. 결과의 척도로, 그는 ``최악의'' 줄의 문자 수가 원하는 $n$자에서 벗어난 정도를 정의한다. 그는 이제 이 척도를 최소화하려고 한다.

글을 읽고, 위 척도가 최소화되도록 정한 위치에서 줄을 바꾸어 출력하는 프로그램을 작성한다.

입력의 첫째 줄에는 각 줄에 들어갈 수 있는 문자 수를 나타내는 정수 $n$ ($1 \leq n \leq 80$)이 주어진다.

다음 줄에는 단어 수를 나타내는 정수 $k$ ($1 \leq k \leq 1000$)이 주어진다.

이어서 각 줄에 단어 $s$ ($1 \leq |s| \leq \min(n, 20)$)가 하나씩 있는 $k$개의 줄이 주어진다. 단어에는 문장 부호와 문자 a-z 및 A-Z가 포함되지만, 단어 자체에는 공백이 포함될 수 없다. 문장 부호는 단어의 일부로 취급하며 단어에서 분리할 수 없다. 출력해야 하는 글은 이 $k$개의 단어를 정확히 이 순서대로 나열한 것이다.

$n$에서 벗어난 정도의 최댓값이 최소화되도록 줄을 바꾸어 글을 출력한다. 같은 줄에 있는 연속한 단어 사이에는 정확히 하나의 공백이 있어야 한다.