Problem Description

Tenka-kun has prepared $N$ pieces of meat. Each piece of meat is a long, thin shape with dimensions $L$ cm in width and $1$ cm in height, divided into $L$ parts of $1$ cm squares. Each part has a defined hardness, and the hardness of the $j$-th part from the left of the $i$-th piece of meat is denoted as $a_{i,j}$. The $N$ pieces of meat are placed vertically in a row with their left edges aligned.

Tenka-kun intends to create a skewer by piercing all the pieces of meat vertically with a single skewer. Tenka-kun can perform the following operations:

1. Shift any one piece of meat $k$ cm to the left or right. $k$ must be an integer, and this operation incurs a cost of $k^2$. However, the same piece of meat cannot be shifted more than once.
2. After shifting the pieces of meat, insert the skewer vertically at a certain position. All pieces of meat must be pierced by the skewer. The cost is determined by the hardness of the part where the skewer pierces each piece of meat (since the skewer is very thin, it pierces only one part of each piece).

Find the minimum total cost required to skewer all the pieces of meat.

Input Format

The input is given from the standard input in the following format:

$N$ $L$ $a_{1,1}$ … $a_{i,L}$ : $a_{N,1}$ … $a_{N,L}$

Output Format

Determine the minimum total cost required to skewer all $N$ pieces of meat.

Sample Input and Output

Sample Input #1

2 3
1 5 6
5 3 1

Sample Output #1

4

Sample Input #2

3 4
1 3 5 2
8 3 5 7
3 5 1 4

Sample Output #2

7

Sample Input #3

4 5
8 12 20 9 15
5 4 8 15 12
20 18 10 3 9
15 7 13 14 4

Sample Output #3

25

Notes/Hints

Constraints

• $1 \leq N \leq 100$
• $1 \leq L \leq 10000$
• $1 \leq a_{i,j} \leq 10^9$

Sample Explanation 1

By shifting the first piece of meat $1$ cm to the right and the second piece of meat $1$ cm to the left, and then piercing the skewer through the first part of the first piece of meat, the cost of shifting is $1+1$, and the cost of piercing the meat is $1+1$, resulting in a total cost of $4$. There is no way to skewer the meat with a cost less than $4$.

见题面 Input 部分

见题面 Output 部分