又到了一年一度的明明生日了，明明想要买B样东西，巧的是，这B样东西价格都是A元。 但是，商店老板说最近有促销活动，也就是： 如果你买了第I 样东西，再买第J样，那么就可以只花 K（I,J）元，更巧是， K（I,J）竟然等于 K（J,I）。 现在明明想知道，他最少要花多少钱。

第一行两个整数，A,B。 接下来B行，每行B个数，第I行第 J个为 KI,J 我们保证 KI,J=KJ,I，并且 K I,I=0。 特别的，如果K I,J =0，那么表示这两样东西之间不会导致优惠。

一个整数，为最小要花的钱数。 输入输出样例