Death Note

Light has recovered the Death Note and plans to write the names of n people in it. The names must be written in the given order.

The note has m cells in each row. Names are written from top to bottom, and within a row from left to right. When two names are written on the same row, exactly one blank cell must be placed between them. If the next name cannot fit completely in the remaining cells of the current row, it must start on the next row.

For every row except the last row, count the number of unused cells at the end of that row. The cost is the sum of the squares of those unused counts. The last row is not counted because more names may be written later. Find the minimum possible cost.

The first line contains two integers n and m (1 <= n <= 1,000, 1 <= m <= 1,000). Here, m is the number of cells in each row of the note.

Each of the next n lines contains the length of one person's name, in the order the names must be written. Every length is a positive integer not greater than m.

Print the minimum possible sum of squared unused cells.