영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Pelle has a text on his computer that he now wants to edit and print. He wants the printout in a “monospaced” font. That is, all characters have the same width (take up the same amount of space on a line). Additionally, he wants to fit the printout to a given line length, n characters per line.
He realizes that it is hardly possible to make every line contain exactly n characters, since there must be exactly one space between two words. However, he is satisfied if he manages to format the printout so that it comes as close to the desired result as possible. As a measure of the result, he defines the deviation in number of characters of the “worst” line from the desired n characters. He now wants to minimize this measure.
Write a program that reads the text and prints it with line breaks at positions such that the above measure is minimized.
Input
The first line of input contains the integer n (5 ≤ n ≤ 80), the desired line length.
The next line contains the integer k (1 ≤ k ≤ 1000), the number of words.
Then follow k lines with one word s (1 ≤ |s| ≤ 20) on each line. The words contain punctuation and the letters a-z and A-Z, but the words themselves cannot contain spaces. Punctuation is treated as part of the word and may not be separated from it. The text you should print consists of these k words in this exact order.
Output
Print the text with line breaks such that the maximum deviation from n is minimized. There must be exactly one space between consecutive words on the same line. If there are several optimal printouts, any one of them will be accepted.
예제
예제 1
30 32 Hej mor och far! Har ar det varmt och skont, solen lyser var dag och det ar varmt i vattnet! Just nu ligger jag pa stranden och laser en bok. Halsningar Pelle
Hej mor och far! Har ar det varmt och skont, solen lyser var dag och det ar varmt i vattnet! Just nu ligger jag pa stranden och laser en bok. Halsningar Pelle