0624 - エナジードリンク

問題

SNS(死んだ魚の目日照不足シャトルラン)部は今, 夏コミに向けてゲームを制作しようとしています。

部員の一員であるSNS部部長の村上椎奈さんはプログラマーです。 椎奈さんは, 夏コミまでに残された N 日の間にゲームを完成するために, それぞれの日で以下の行動を繰り返す決意をしています。

• 朝, プログラミングをする。
• 昼, プログラミングをする。
• 夜, エナジードリンクを 1 本飲んで気合いを入れる。
• 深夜, プログラミングをする。

部員の一員である本田珠輝さんは暇なので, 椎奈さんが飲むエナジードリンクを日中の間に店で買ってくる係になりました。

店では, M 種類のエナジードリンクが無限個売られていて, 毎日その値段が変わります。 i 日目に種類 j のエナジードリンクを購入する時 A_i,j 円かかります。 1 日に同じ種類のエナジードリンクは最大 1 本しか購入できません。 また 1 日に購入するドリンクは 0 本でも構いません。

またこの店では, エナジードリンクの買い占めに警戒して税金をかけています。 1 日に p 個のエナジードリンクを同時に購入すると, p² 円の金額を追加で払う必要があります。

椎奈さんは種類や買った日付を問わずにエナジードリンクを 1 日 1 本飲みます。 但しエナジードリンクがないとき椎奈さんは泣くので, 任意の日の夜においてまだ飲んでいないエナジードリンクは 1 本以上存在するようにしたいです。

椎奈さんと珠輝さんのために, この条件を満たすように上手くエナジードリンクを購入するときの最小金額を求めてください。

入力

N M
A1,1 A1,2 ... A1,M
A2,1 A2,2 ... A2,M
:
AN,1 AN,2 ... AN,M

1 行目に, 日数 N (1 ≤ N ≤ 300) とエナジードリンクの種類数 M(1 ≤ M ≤ 300) が与えられます。

続く N 行 M 列にエナジードリンクの値段の情報が与えられます。 このうち i 行目 j 列目は, i 日目の種類 j のエナジードリンクの値段が C_i,j(1 ≤ C_i,j ≤ 10⁶) 円であることを表します。

出力

条件を満たすように上手くエナジードリンクを購入するときの最小金額を 1 行に出力してください。

入出力例

入力例 1

3 2
1 1
100 100
10000 10000

出力例 1

107

珠輝さんは以下のようにエナジードリンクを購入すれば良いです。

• 1 日目に種類 1 と 2 のエナジードリンクを 1 + 1 + (税金 2²) = 6 円払って購入する。
• 2 日目に種類 1 か 2 のエナジードリンクを 100 + (税金 1¹) = 101 円払って購入する。
• 3 日目は何も購入しない。

6 + 101 = 107 円で, これより安くするような購入の方法は存在しないため 107 を出力します。

入力例 2

5 5
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4

出力例 2

10

1 日に 1 本ずつ 1 円のエナジードリンクを購入するのが最適です。

入力例 3

5 5
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5

出力例 3

18

珠輝さんは以下のようにエナジードリンクを購入すれば良いです。

• 1 日目に 2 本のエナジードリンクを 1 + 1 + (税金 2²) = 6 円払って購入する。
• 2 日目に 2 本のエナジードリンクを 2 + 2 + (税金 2²) = 8 円払って購入する。
• 3 日目に 1 本のエナジードリンクを 3 + (税金 1¹) = 4 円払って購入する。