Problem B: PIPI逛超市

Problem B: PIPI逛超市

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 151  Solved: 24
[Submit] [Status] [Web Board] [Creator:]

Description

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

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

Input

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

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

Kij=0代表买了第i样商品后,买第j样商品无优惠,保证Kij=Kji



Output

输出所花费的最少钱数。

Sample Input

5 3
0 3 2
3 0 4
2 4 0

Sample Output

10