데스노트
시간 제한2초메모리 제한128 MB
고정된 폭의 줄에 단어들을 순서대로 배치하되 단어 사이에 빈칸 하나를 두어야 할 때, 마지막 줄을 제외한 모든 줄의 남은 칸 수 제곱의 합을 최소화합니다.
문제
라이토는 데스노트에 n명의 이름을 적으려 한다. 이름은 주어진 순서 그대로 적어야 한다.
노트의 한 줄은 m칸으로 이루어져 있다. 이름은 위쪽 줄부터 아래쪽 줄로, 같은 줄에서는 왼쪽에서 오른쪽으로 적는다. 같은 줄에 여러 이름을 적을 때는 인접한 두 이름 사이에 빈 칸을 정확히 하나 둔다. 다음 이름이 현재 줄의 남은 칸에 완전히 들어가지 않으면, 그 이름은 반드시 다음 줄부터 적어야 한다.
마지막 줄을 제외한 각 줄에 대해, 줄 끝에 사용하지 않고 남은 칸 수를 센다. 비용은 이 남은 칸 수들을 각각 제곱해 더한 값이다. 마지막 줄은 나중에 더 적을 수 있으므로 비용에 포함하지 않는다. 가능한 비용의 최솟값을 구하라.
입력
첫째 줄에 정수 n과 m이 주어진다 (1 <= n <= 1,000, 1 <= m <= 1,000). m은 노트 한 줄의 칸 수이다.
다음 n개의 줄에는 각 사람의 이름 길이가 적어야 하는 순서대로 하나씩 주어진다. 각 길이는 m을 넘지 않는 자연수이다.
출력
남은 칸 수의 제곱합으로 만들 수 있는 최솟값을 출력한다.