题目描述

暑假当然要出门玩了，西西安排了 $B$ 个城市去旅行，巧的是，从西西家去这些城市的机票花费都是$A$元。

但是，航空公司最近有促销活动，也就是：

如果你买了去第 $I$ 个城市的机票，再买第去 $J$ 个城市的机票，那么就可以只花 $K_{I,J}$ 元，更巧的是，$K_{I,J}$ 竟然等于 $K_{J,I}$。

现在西西想知道，他最少要花多少钱去到所有的城市。

输入格式

第一行两个整数，$A,B$。 接下来 $B$ 行，每行 $B$ 个数，第 $I$ 行第 $J$ 个为 $K_{I,J}$。

输出格式

一个整数，为最小要花的钱数。

样例 #1

样例输入 #1

1 1
0

样例输出 #1

1

样例 #2

样例输入 #2

3 3
0 2 4
2 0 2
4 2 0

样例输出 #2

7

数据规模

对于 $30\%$ 的数据，$1\le B\le 10$。

对于 $100\%$ 的数据，$1\le B\le500,0\le A,K_{I,J}\le1000$。