题目描述

A市迎来了当地的传统节日——一年一度的观星节。

主办方请来了著名绘画大师大D画下了当晚天上的 $n$ 颗星星，参与者可以花费 $m$ 点星光能量为任意一颗星星点一盏灯。

除此之外，主办方还制作了一个 $n \times n$ 的表格，表格中第 $i$ 行第 $j$ 列的数字 $F_{i,j}$ 表示如果目前第 $i$ 颗星星是亮的，那么可以花费$F_{i,j}$点星光能量为第 $j$ 颗星星点亮一盏灯。特别地，对于任何 $a$，$b$，$F_{a,b}$ 总是等于$F_{b,a}$ 。

大D看着这些灯，心里盘算着最少花费多少星光能量能够为所有的星星点一盏灯。

输入格式

第一行两个整数$m$，$n$，含义如题所示。

接下来$n$行，每行$n$个整数，第$i$行第$j$个整数表示$F_{i,j}$。

输出格式

一行整数，输出点亮所有灯所需最少的星光能量。

样例输入 #1

5 3
3 2 3
2 4 1
3 1 4

样例输出 #1

8

样例输入 #2

10 5
6 2 3 5 2 
2 4 1 5 7 
3 1 3 4 3 
5 5 4 3 6 
2 7 3 6 4

样例输出 #2

19

数据范围

【样例 1 解释】

在样例1中，先支付$5$点星光能量点亮第二颗星星的灯，然后通过$F_{2,1}$和$F_{2,3}$点亮第一课和第三颗星星的灯。总共花费了$m+F_{2,1}+F_{2,3}=5+2+1=8$点星光能量。

对于$100\%$的数据，$1 \le m,F_{a,b} \le 1000$