#include <bits/stdc++.h>
using namespace std;
int a,n;
struct aa{
	int i1,j1,quan;
}ma[260000];
int f[505];
int main(){
	cin>>a>>n;
	int x,c=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>x;
			if(x==0||x>a)x=a;
			ma[c].i1=i;ma[c].j1=j;ma[c].quan=x;
			c++;
		}
	}
	c--;
	for(int i=1;i<=c;i++){
		for(int j=i+1;j<=c;j++){
			if(ma[i].quan>ma[j].quan){
				swap(ma[i],ma[j]);
			}
		}
	}
	int sum=a,k=0;
	for(int i=1;i<=c;i++){
		if((f[ma[i].i1]==0||f[ma[i].j1]==0)&&ma[i].i1!=ma[i].j1){
			sum+=ma[i].quan;
			if(f[ma[i].i1]==0){
				f[ma[i].i1]=1;k++;
			}
			if(f[ma[i].j1]==0){
				f[ma[i].j1]=1;k++;
			}
		}
		if(k==n){
			break;
		}
	}
	cout<<sum;
	return 0;
}