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}。
一行整数，输出点亮所有灯所需最少的星光能量。
5 3 3 2 3 2 4 1 3 1 4
8
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
19
在样例 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
| 测试点编号 | n |
|---|---|
| 1∼2 | \le 4 |
| 3∼6 | \le 100 |
| 7∼10 | \le 1000 |