题目描述

又到了一年一度的明明生日了，明明想要买 $n$ 样东西，巧的是，这 $n$ 样东西价格都是 $a$ 元。

但是，商店老板说最近有促销活动，也就是：

如果你买了第 $i$ 样东西，再买第 $j$ 样，那么就可以只花 $w_{i,j}$ 元，更巧的是，$w_{i,j}$ 竟然等于 $w_{j,i}$。

现在明明想知道，他最少要花多少钱。

输入格式

第一行两个整数，$n,a$。

接下来 $n$ 行，每行 $n$ 个数，第 $i$ 行第 $j$ 个为 $w_{i,j}$。

我们保证 $w_{i,j}=w_{j,i}$ 并且 $w_{i,i}=0$。

特别的，如果 $w_{i,j}=0$，那么表示这两样东西之间不会导致优惠。

数据规模

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

对于 $100\%$ 的数据，$1\le n \le500$ , $0 \le a,w_{i,j}\le1000$。

输出格式

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

样例

1 1
0

1

3 3
0 2 4
2 0 2
4 2 0

7

样例解释

样例 $2$：先买第 $2$ 样东西，花费 $3$ 元，接下来因为优惠，买 $1,3$ 样都只要 $2$ 元，共 $7$ 元。

（同时满足多个“优惠”的时候，聪明的明明当然不会选择用 $4$ 元买剩下那件，而选择用 $2$ 元。）