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>

#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif

using namespace std;

#define REP(i, a, b) for(int i = (a); i < int(b); ++i)
#define rep(i, n) REP(i, 0, n)
#define ALL(x) begin(x), end(x)

template<class T> inline void chmax(T &a, const T &b) { if(a < b) a = b; }
template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }

struct SCC {
	typedef vector<vector<int>> graph;

	int V;
	graph G;
	vector<int> cmp;
	vector<int> vs;
	vector<bool> used;

	SCC(int V_):V(V_), G(V_), cmp(V_), used(V_) {}
	SCC(const graph &G_):V(G_.size()), G(G_), cmp(V), used(V) {}

	void add_edge(int from, int to) {
		G[from].emplace_back(to);
	}

	void dfs(int v) {
		used[v] = true;
		for(const auto &to : G[v]) {
			if(!used[to]) dfs(to);
		}
		vs.emplace_back(v);
	}

	void rdfs(int v, int k, graph &rG) {
		used[v] = true;
		cmp[v] = k;
		for(const auto &to : rG[v]) {
			if(!used[to]) rdfs(to, k, rG);
		}
	}

	int scc() {
		vs.clear();
		fill(used.begin(), used.end(), false);

		for(int v = 0; v < V; ++v) {
			if(!used[v]) dfs(v);
		}

		graph rG(V);
		for(int v = 0; v < V; ++v) {
			for(const auto &to : G[v]) {
				rG[to].emplace_back(v);
			}
		}

		fill(used.begin(), used.end(), false);
		int k = 0;
		for(int i = static_cast<int>(vs.size()) - 1; i >= 0; --i) {
			if(!used[vs[i]]) rdfs(vs[i], k++, rG);
		}
		return k;
	}
};

typedef double weight;
constexpr weight INF = (1 << 28);

struct edge {
	int to;
	weight cost;
	edge(int to_, weight cost_):to(to_), cost(cost_){}
};

typedef vector<vector<edge>> weighted_graph;

weight minimum_spanning_arborescence(int r, const weighted_graph &G, weight sum = 0) {
	const int n = G.size();

	vector<int> rev(n, -1);
	vector<weight> minimum_weight(n, INF);
	for(int v = 0; v < n; ++v) {
		for(const auto &e : G[v]) {
			if(minimum_weight[e.to] > e.cost) {
				minimum_weight[e.to] = e.cost;
				rev[e.to] = v;
			}
		}
	}

	SCC scc(n);
	for(int v = 0; v < n; ++v) {
		if(v == r) continue;
		if(rev[v] == -1) return INF;
		scc.add_edge(rev[v], v);
		sum += minimum_weight[v];
	}

	const int num = scc.scc();
	if(num == n) return sum;

	weighted_graph next_G(num);
	for(int v = 0; v < n; ++v) {
		const int from = scc.cmp[v];
		for(const auto &e : G[v]) {
			const int to = scc.cmp[e.to];
			if(from == to) continue;

			const auto cost = e.cost - minimum_weight[e.to];
			next_G[from].emplace_back(to, cost);
		}
	}

	return minimum_spanning_arborescence(scc.cmp[r], next_G, sum);
}

typedef vector<weight> vec;

inline weight dot(const vec &a, const vec &b) {
	weight res = 0.0;
	for(int i = 0; i < a.size(); ++i) {
		res += a[i] * b[i];
	}
	return res;
}

inline weight norm(const vec &v) {
	return dot(v, v);
}

inline weight calc(const vec &a, const vec &b) {
	constexpr double EPS = 1e-9;
	const auto n = norm(a);
	if(abs(n) < EPS) return norm(b);

	const weight r = dot(a, b) / n;
	weight res = 0.0;
	for(int i = 0; i < a.size(); ++i) {
		const weight t = b[i] - r * a[i];
		res += t * t;
	}
	return res;
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout.precision(10);
	cout.flags(ios::fixed);

	int d, n;
	cin >> d >> n;

	vector<vec> vectors;
	vectors.reserve(n);

	for(int i = 0; i < n; ++i) {
		vec v(d);
		for(auto &e : v) cin >> e;
		vectors.emplace_back(v);
	}

	weighted_graph G(n + 1);
	G[n].reserve(n);
	for(int i = 0; i < n; ++i) {
		G[n].emplace_back(i, norm(vectors[i]));
	}

	for(int i = 0; i < n; ++i) {
		G[i].reserve(n - 1);

		for(int j = 0; j < n; ++j) {
			if(i == j) continue;
			G[i].emplace_back(j, calc(vectors[i], vectors[j]));
		}
	}

	cout << minimum_spanning_arborescence(n, G) << endl;

	return EXIT_SUCCESS;
}