問題文

天下一くんは $N$ 個の肉を用意しました。それぞれの肉は横$L$cm × 縦$1$cmの細長い形をしており、$L$個の$1$cm四方の部分に分かれています。それぞれの部分ごとに肉の硬さが決まっており、$i$番目の肉の左から$j$番目の部分の硬さを$a_{i,j}$とおきます。 $N$個の肉は、左端を揃えて上から順に縦に並べて置かれています。

天下一くんは、すべての肉を縦方向の$1$本の串により刺して串刺しを作ろうとしています。天下一くんは

1. 肉のうちいずれか$1$つを左または右に$k$cmずらす、という操作を好きな回数行います。$k$は整数でなければいけません。このとき、コスト$k^2$がかかります。ただし、同じ肉に対して$2$回以上ずらす操作を行ってはいけません。
2. 肉をずらした後、ある位置に縦に串を刺します。串に突き刺さらない肉があってはいけません。それぞれの肉に対し、串が刺さった部分(串は十分細いため、いずれか$1$つの部分に突き刺さるものとします)の硬さだけコストがかかります。

コストの総和の最小値を求めてください。

制約

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

入力例 1Copy

2 3
1 5 6
5 3 1

出力例 1Copy

4

$1$つ目の肉を$1$cm右にずらし、$2$つ目の肉を$1$cm左にずらした上で、$1$つ目の肉の左から$1$つ目の部分に刺さるように串刺しにすると、ずらしたコストが$1+1$、突き刺した肉の硬さで$1+1$のコストがかかるため、合計$4$となります。コスト$4$未満で串刺しにする方法はありません。

入力例 2Copy

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

出力例 2Copy

7

入力例 3Copy

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

出力例 3Copy

25