Problem: You are recording a result of a secret experiment, which consists of a large set of N-dimensional vectors. Since the result may become very large, you are thinking of compressing it. Fortunately you already have a good compression method for vectors with small absolute values, all you have to do is to preprocess the vectors and make them small.

You can record the set of vectors in any order you like. Let's assume you process them in the order v_1, v_2,..., v_M. Each vector v_i is recorded either as is, or as a difference vector. When it is recorded as a difference, you can arbitrarily pick up an already chosen vector v_j (j<i) and a real value r. Then the actual vector value recorded is (v_i - r v_j). The values of r and j do not affect the compression ratio so much, so you don't have to care about them.

Given a set of vectors, your task is to write a program that calculates the minimum sum of the squared length of the recorded vectors.



Input

The input is like the following style.

N M
v_{1,1} v_{1,2} ... v_{1,N}
...
v_{M,1} v_{M,2} ... v_{M,N}


The first line contains two integers N and M (1 \leq N, M \leq 100), where N is the dimension of each vector, and M is the number of the vectors. Each of the following M lines contains N floating point values v_{i,j} (-1.0 \leq v_{i,j} \leq 1.0) which represents the j-th element value of the i-th vector.

Output

Output the minimum sum of the squared length of the recorded vectors. The output should not contain an absolute error greater than 10^{-6}.

Examples

Input

2 3
1.0 1.0
-1.0 0.0
0.5 0.5


Output

1.0


Input

1 1
1.0


Output

1.0


Input

4 3
1.0 1.0 0.0 0.0
-1.0 0.0 -1.0 0.0
0.5 0.5 0.5 0.5


Output

3.0

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt" > "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\b.answer"

typedef double Weight;

struct Edge {
	int src, dst;
	Weight weight;
	int id;
	Edge(int src_, int dst_, Weight weight_,const int id_) :
		src(src_), dst(dst_), weight(weight_),id(id_) { }
	Edge(int src, int dst, Weight weight) :
		src(src), dst(dst), weight(weight) { }
	Edge() :src(0), dst(0), weight(0) {

	}
};
const Weight INF = 1e18;
const Weight ZERO = 0;
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
ld getdis(const vector<ld>&f, const vector<ld>&t) {
	ld amin = -1e9;
	ld amax = 1e9;
	int n = 100;
	while (n--) {
		ld amid0 = (amin*2 + amax) /3;
		ld amid1 = (amin + amax * 2) / 3;
		ld len0 = 0;
		ld len1 = 0;
		{
		
			for (int i = 0; i < f.size(); ++i) {
				len0 += (t[i] - amid0*f[i])*(t[i] - amid0*f[i]);
			}
			for (int i = 0; i < f.size(); ++i) {
				len1 += (t[i] - amid1*f[i])*(t[i] - amid1*f[i]);
			}
		}
		if (len0<len1) {
			amax = amid1;
		}
		else {
			amin = amid0;
		}
		if (!n)return len0;
	}
}

namespace getcycle {
	pair<int,vector<Edge>> dfs(const Graph&g,vector<int>&used,const int now,const int id) {
		if (used[now]==-1) {
			used[now] = id;
			for (auto e : g[now]) {
				if (used[e.dst] ==id) {
					return make_pair(e.dst, vector<Edge>(1, e));
				}else if (used[e.dst]!=-1) {
					continue;
				}
				else {
					assert(used[e.dst] == -1);
					auto p(dfs(g, used, e.dst,id));
					if (p.first == -1) {
						return p;
					}
					else if (p.first == -2) {
						continue;
					}
					else {
						p.second.push_back(e);
						if (p.first == now) {
							return make_pair(-1, p.second);
						}
						else {
							return p;
						}
					}
				}
			}
			return make_pair(-2, vector<Edge>(0));
		}
		else {
			assert(false);
			return make_pair(0,vector<Edge>(0));
		}
	}
	vector<Edge>get_cycle(const Graph&g,const int start) {
		vector<int>used(g.size(),-1);
		
		int id = 0;
		for (int i = 0; i < g.size(); ++i) {
			if (used[i]==-1) {
				
				vector<Edge>cycles = dfs(g, used, i,id).second;
				id++;
				if (!cycles.empty()) {

					reverse(cycles.begin(), cycles.end());
					return cycles;
				}
			}
		}
		return vector<Edge>(0);
	}
}

//aoj2309???varify??????????????£??????????????§????????????????????????
pair<Weight,Graph> chu_liu(const Graph&g, const int start,const int e_size) {

	Graph tree(g.size());
	ld total_len = 0;
	{
		Graph revg(g.size());


		for (auto es : g) {
			for (auto e : es) {
				revg[e.dst].emplace_back(e.dst, e.src, e.weight);
			}
		}
		for (int node = 0; node < g.size(); ++node) {
			if (node == start)continue;
			else {
				Weight amin = INF;
				Edge min_edge;
				for (auto reve : revg[node]) {
					if (amin > reve.weight) {
						amin = reve.weight;
						min_edge = Edge(reve.dst, reve.src, reve.weight);
					}
				}
				if (amin < INF) {
					total_len += min_edge.weight;
					tree[min_edge.src].emplace_back(min_edge);
				}
			}
		}
	}
	vector<Edge>cycle_edges(getcycle::get_cycle(tree, start));
	
	if (cycle_edges.empty()) {
		return make_pair(total_len,g);
	}
	else {
		vector<bool>node_is_cycle(g.size());

		/*????´???°???Edge?????°????????§??????*/
		vector<int>edge_is_cycle(e_size);

		vector<Weight>prev_lens(g.size(), ZERO);
		
		for (auto ce : cycle_edges) {
			node_is_cycle[ce.src] = true;
			prev_lens[ce.dst] = ce.weight;
		}
		Graph newg(g.size());
		const int compress = cycle_edges[0].src;
		int ne_size = 0;
		/*????´???°???Edge?????°????????§??????*/
		vector<Edge>memo(e_size);
		for (int s = 0; s < g.size();++s){
			bool src_is_cycle = node_is_cycle[s];
			for (auto e : g[s]) {
				memo[e.id] = e;
				bool dst_is_cycle = node_is_cycle[e.dst];
				if (src_is_cycle&&dst_is_cycle) {
					continue;
				}
				else if (src_is_cycle) {
					e.src = compress;
				}
				else if (dst_is_cycle) {
					e.weight -= prev_lens[e.dst];
					e.dst = compress;
				}
				newg[e.src].push_back(e);
			}
		}
		auto p=chu_liu(newg, start, e_size);
		Graph compress_tree(p.second);
		Graph ans_tree(g.size());
		for (auto es : compress_tree) {
			for (auto e : es) {
				const Edge prev_edge(memo[e.id]);
				ans_tree[prev_edge.src].emplace_back(prev_edge);
			}
		}
		Weight cycle_len = 0;
		for (auto e : cycle_edges) {
			cycle_len += e.weight;
		}
		return make_pair(p.first + cycle_len, ans_tree);
	}
}

int main() {
	int N, M; cin >> N >> M;
	vector<vector<ld>>vecs(M,vector<ld>(N));
	vector<vector<ld>>edges(M, vector<ld > (M));
	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> vecs[i][j];
		}
	}
	const int start = 0;
	const int node = 1;
	Graph g(M+1);
	int id = 0;
	for (int i = 0; i < M; ++i) {
		ld inidis = 0;
		for (int j = 0; j < N; ++j) {
			inidis += vecs[i][j] * vecs[i][j];
		}
		g[start].emplace_back(start, node + i, inidis,id++);
		for (int j = 0; j < M; ++j) {
			if (i != j) {
				ld dis = getdis(vecs[i], vecs[j]);
				g[node + i].emplace_back(node + i, node + j, dis, id++);
			}
		}
	}
	auto p=chu_liu(g, start,(g.size())*((g.size()+1)));
	cout <<fixed<<setprecision(22)<< p.first << endl;
	return 0;
}