一年一度的双十一购物又节到了，为了吸引客户，某店铺推出了一个活动。
活动规则如下:
如果你购买第i件商品，再购买第j件商品，那么你就只需花费K(i,j)元购买第j件商品;
反之亦然，即如果你购买第j件商品，再购买第i件商品,你需要花费K(j,i)元购买第i件商品，并且K(i,j)=K(j,i)。
当然你也可以选择只购买某一件商品。
小明想要在此店铺购买m件商品，并且巧合的是这m件商品每件都是p元，求最少需要花费多少元购入这m件商品。
输入
输入共m+1行。
第一行为两个整数p和m。
接下来的m行，每行m个数，第i行第j个为K(i,j)。
输出
输出共一行。
一个整数,为最小花费数。
样例
| 标准输入 复制文本 |
1 1 0 |
| 标准输出 复制文本 |
1 |
| 标准输入 复制文本 |
3 3 0 2 4 2 0 2 4 2 0 |
| 标准输出 复制文本 |
7 |
提示
数据范围:
1<=m<=500
0<=p,K(i,j)<=1000
样例解释:
样例一:
只需购买一件商品，此时的最小花费数为1。
样例二:
先买第 2 样东西，花费 3 元，接下来因为优惠，买 1,3样都只要 2 元，共 7 元。