PIPI家镇上有一家超市，有一天PIPI想去超市买n样东西，这n样东西在超市都是m元，但是老板说最近有促销活动，如果你买了第i样东西，那么再买第j样时就可以只花K_ij元。

现在PIPI想知道，他购买这n样东西最少要花多少钱。

第一行两个正整数m和n。m<=1000,n<=500

接下来输入一个n*n的矩阵K，K_ij(不超过1000)代表已经买了第i样商品后，就可以用K_ij的价格来买第j样商品。

K_ij=0代表买了第i样商品后，买第j样商品无优惠，保证K_ij=K_ji。