問題文

maguro君は謎解きが大好きです。同じく謎解きが好きな先輩のために、maguro君は謎解きビンゴを作りました。

ビンゴは $N \times N$ マスの用紙を使って行われます。上から $i$ 行目、左から $j$ 列目のマスを $(i,j) \ (1 \leq i,j \leq N)$ とします。

それぞれのマスには謎が書かれており、 $(i,j)$ を開くためには、 $A_{i,j}$ の知力を消費してそのマスの謎を解く必要があります。

通常、一列でも揃えばビンゴですが、maguro君はただのビンゴでは満足しません。 $N$ 本の列、 $N$ 本の行、 $2$ 本の対角線のうち、それの上にあるマス $N$ 個全て開いているものが $M$ 本以上ある必要があります。

このとき、条件を満たすようにするために消費する知力の総和の最小値を求めてください。

（2021/3/24）問題文を一部修正しました。

入力

$N\ M$
$A_{1,1}\ A_{1,2}\ \cdots\ A_{1,N - 1}\ A_{1,N}$
$A_{2,1}\ A_{2,2}\ \cdots\ A_{2,N - 1}\ A_{2,N}$
$\vdots$
$A_{N,1}\ A_{N,2}\ \cdots\ A_{N,N - 1}\ A_{N,N}$

• 入力は全て整数である。
• $2 \leq N \leq 16$
• $1 \leq M \leq 2N + 2$
• $1 \leq A_{i,j} \leq 100\ (1 \leq i,j \leq N)$

出力

条件を満たすようにするために消費する知力の総和の最小値を出力してください。最後に改行してください。

サンプル

3 2
3 1 4
1 5 9
2 6 5

11

4 3
1 9 3 2
4 1 2 5
7 2 1 6
2 9 8 1

21