Subtitle Reflow Penalty Minimum

A live-captioning system displays a transcript, word by word and in order, on a screen that can show at most k characters per caption line. You must lay the words out into consecutive caption lines: every word appears on exactly one line, the words on a line keep their original left-to-right order, consecutive words on the same line are separated by exactly one space, and a line may not begin or end with a space. A line's length is its total character count, letters and internal spaces together, and it must never exceed k. (It is guaranteed that no single word is longer than k characters, so some valid layout always exists.)

Every caption line except the very last one used contributes a readability penalty of (k - length)^2, where length is that line's character count; the last line contributes no penalty at all, however short it is. Given the transcript and k, find the minimum possible total readability penalty over all valid layouts.

Input format

• Line 1: a single integer k.
• Line 2: the transcript — one or more lowercase words separated by single spaces (no leading or trailing space, no two consecutive spaces).

Output format

Print a single integer: the minimum total readability penalty.

Constraints

• 1 <= length of the transcript line (characters, including spaces) <= 500
• 1 <= k <= 500
• every word in the transcript has length <= k
• the transcript consists only of lowercase English letters and single spaces separating words

9
the fox runs fast

4

11
hello world

0