問題文

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

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

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

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

制約

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

入力例 1

2 3
1 5 6
5 3 1

出力例 1

4

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

入力例 2

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

出力例 2

7

入力例 3

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

出力例 3

25