KLU

/** *  ZADANIE KUL * *  Uzyty algorytm znaleziony gdzies w odmetach Dysku: *  Znajdowanie maksymalnego skojarzenia o minimalnej wadze ( plik stworzony VII 06r ) */#include <iostream>#define INFINITE 100000000#define MXN 510using namespace std;int n;int pair_left[MXN] , pair_right[MXN];int label_left[MXN], label_right[MXN];int delta[MXN], has_delta[MXN];int kol[MXN];int tab[MXN][MXN];void concatLanes(int x) {	int tmp;	while (x != -1) {		pair_right[x] = has_delta[x];		tmp = pair_left[pair_right[x]];		pair_left[pair_right[x]] = x;		x = tmp;	}}long long kojarz() {	int matching = 0;		for (int i = 0; i < n; i++ ) {		pair_left [i]  = -1;		pair_right[i] = -1;				label_left [i] = INFINITE;		label_right[i] = 0;				for (int b = 0; b < n; b++ )		    //Get shorter path			label_left[i] = min(label_left[i], tab[i][b]);	}		bool tmp = true;	int h, t;		while (matching < n) {		if (tmp) {			h = 0;			t = 0;						for (int i = 0; i < n; i++ ) {				delta    [i] = INFINITE;				has_delta[i] = -1;								if (pair_left[i] == -1)					kol[t++] = i;			}						tmp = false;		}				while (h < t && !tmp) {			int cur = kol[h++];						for (int i = 0; i < n && !tmp; i++ )				if (pair_left[cur] != i && tab[cur][i] - (label_left[cur] + label_right[i]) < delta[i]) {					delta[i] = tab[cur][i] - (label_left[cur] + label_right[i]);					has_delta[i] = cur;										if (delta[i] == 0) {						if (pair_right[i] == -1) {							concatLanes(i);							matching++;							tmp = true;						} else							kol[t++] = pair_right[i];					}				}		}				if (!tmp) {			int _delta = INFINITE;			for (int i = 0; i < n; i++ )				if (delta[i] != 0)					_delta = min(_delta, delta[i]);			for (int i = 0; i < t; i++ )				label_left[kol[i]] += _delta;			for (int i = 0; i < n; i++ )				if (delta[i] == 0)					label_right[i] -= _delta;				else {					delta[i] -= _delta;										if (delta[i] == 0 && !tmp) {						if (pair_right[i] == -1) {							concatLanes(i);							matching++;							tmp = true;						} else							kol[t++] = pair_right[i];					}				}		}	}		long long ret = 0;	for (int i = 0; i < n; i++ ) {		ret += label_left[i] + label_right[i];		    }	return ret;}void readData ( ) {    int l, N;	scanf("%d%d", &n, &l);		for ( int i=0; i<=n; ++i ) {    	for ( int j=0; j<=n; ++j ) {    	    tab [ i ] [ j ] = 0;    	}    }		for (int i=0; i<l; ++i ) {	    scanf ( "%d", &N );	    bool tabl [ n + 7];	    for ( int p=0; p<=n; ++p ) {	        tabl[p]=false;	    }	    	    for ( int pos=N-1; pos>=0; --pos ) {	        int team;        	        scanf ( "%d", &team );	        --team;	        	        //cout << pos << endl;	        for ( int less=pos-1; less>=0; --less ) {	            tab [ team ] [ less ] += pos - less;	        }	        for ( int less=pos+1; less<n; ++less ) {	            tab [ team ] [ less ] += less - pos; 	        }	        	        tabl [ team ] = true;	    }	    	    for ( int x=0; x<n; ++x ) {	        if ( ! tabl [ x ] ) {	            for ( int v=0; v<=n; ++v ) {	                tab [ x ] [ v ] += v + 1;	            }	        }	    }	}	//cout << endl << endl;	/*	for ( int i=0; i<n; ++i ) {    	for ( int j=0; j<n; ++j ) {    	    //cout << tab [ i ] [ j ] << " ";    	}    	    	//cout << endl;    }	*/	/*for (int a = 0; a < n; a++ ) {		int cur =  a + 1;		for (int b = 1; b <= n; b++ )			tab[a][b-1] = cost(cur, b);	}*/}int main() {    readData();	long long ret = kojarz();       printf("%lld\n", ret);	return 0;}