题目背景

强哥是一位热爱生活的工程师，他的好朋友小明的生日快到了。强哥打算给小明买 $B$ 件礼物，巧的是，这 $B$ 件礼物的单价都是 $A$ 元。

商店正在举办促销活动，规则是：如果你已经买了第 $I$ 件礼物，那么再买第 $J$ 件礼物时，只需要支付 $K_{I,J}$ 元（而不是原价 $A$ 元）。

现在强哥想知道，要买齐这 $B$ 件礼物，最少需要花多少钱。

输入格式

第一行两个整数 $A, B$，表示每件礼物的原价和礼物的种类数。

接下来 $B$ 行，每行 $B$ 个数，第 $I$ 行第 $J$ 个数为 $K_{I,J}$，表示如果先买了第 $I$ 件，那么再买第 $J$ 件时可以享受的优惠价格。

数据保证 $K_{I,I}=0$。如果 $K_{I,J}=0$，表示这两件礼物之间不存在优惠关系。

输出格式

一个整数，表示买齐所有礼物最少需要花的钱数。

1 1
0

1

3 3
0 2 4
2 0 2
4 2 0

7

样例解释

样例 2 的一种最优方案：
先按原价 $3$ 元买第 $2$ 件礼物，接下来因为优惠，买第 $1$ 件和第 $3$ 件都只需要 $2$ 元，总花费 $3+2+2=7$ 元。

（当同时满足多个优惠条件时，强哥当然会选择最优惠的那个价格。）

数据范围

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