题目描述

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

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

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

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

输入格式

第一行两个整数 $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≤m,F_{a,b}​ ≤1000$

测试点编号 n

1∼2 ≤4 3∼6 ≤100 7∼10 ≤1000