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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 105

enum Type{
	NONE,
	START,
	FINISH,
};

struct Heap{
	Heap(){
		left = NULL;
		right = NULL;
		diff = 0;
		cost = 0;
		edge_id = 0;
	}

	Heap(double arg_cost,double arg_edge_id){
		left = NULL;
		right = NULL;
		diff = 0;
		cost = arg_cost;
		edge_id = arg_edge_id;
	}
	Heap *left,*right;
	int edge_id;
	double cost,diff;
};

struct Edge{
	Edge(int arg_from,int arg_to,double arg_cost){
		from = arg_from;
		to = arg_to;
		cost = arg_cost;
	}
	int from,to;
	double cost;
};

int V,E;
int boss[NUM];
int table_index;
int FROM[NUM];
double from_cost[NUM];
vector<Edge> edge;
Heap heap_table[10005];
Heap* HEAP[NUM];
Type type[NUM];


void lazy(Heap* A){

	if(A->left){
		A->left->diff += A->diff;
	}
	if(A->right){
		A->right->diff += A->diff;
	}
	A->cost += A->diff;
	A->diff = 0;
}


Heap* meld(Heap* A,Heap* B){

	if(!A){
		return B;
	}
	if(!B){
		return A;
	}

	if((A->cost+A->diff) > (B->cost+B->diff)){
		swap(A,B);
	}

	lazy(A);

	A->right = meld(A->right,B);
	swap(A->left,A->right);

	return A;
}

Heap* pop(Heap *A){
	lazy(A);
	return meld(A->left,A->right);
}



int get_boss(int id){
	if(boss[id] == id)return id;
	else{
		return boss[id] = get_boss(boss[id]);
	}
}

int is_same(int x,int y){
	return get_boss(x) == get_boss(y);
}

void unite(int x,int y){
	int boss_x = get_boss(x);
	int boss_y = get_boss(y);

	if(boss_x == boss_y)return;

	boss[boss_x] = boss_y;
}

void init(){

	for(int i = 0; i < V; i++){
		boss[i] = i;
	}
}

double MCA(int root){

	init();
	table_index = 0;

	for(int i = 0; i < V; i++){
		type[i] = NONE;
		HEAP[i] = NULL;
	}
	type[root] = FINISH;

	for(int i = 0; i < edge.size(); i++){

		heap_table[table_index] = Heap(edge[i].cost,i);
		HEAP[edge[i].to] = meld(HEAP[edge[i].to],&heap_table[table_index++]);
	}

	double ret = 0;

	for(int start = 0; start < V; start++){

		if(type[start] != NONE)continue;

		int current = start;
		vector<int> USED;

		while(type[current] != FINISH){

			type[current] = START;
			USED.push_back(current);

			if(!HEAP[current]){
				return BIG_NUM;
			}

			FROM[current] = get_boss(edge[HEAP[current]->edge_id].from);

			from_cost[current] = HEAP[current]->cost+HEAP[current]->diff;

			HEAP[current] = pop(HEAP[current]);

			if(FROM[current] == current)continue;

			ret += from_cost[current];

			if(type[FROM[current]] == START){

				int tmp = current;

				do{
					if(HEAP[tmp]){
						HEAP[tmp]->diff -= from_cost[tmp];
					}

					if(tmp != current){
						unite(tmp,current);
						HEAP[current] = meld(HEAP[current],HEAP[tmp]);
					}

					tmp = get_boss(FROM[tmp]);

				}while(tmp != current);


			}else{
				current = FROM[current];
			}
		}

		for(int k = 0; k < USED.size(); k++){
			type[USED[k]] = FINISH;
		}
	}
	return ret;
}

int main(){

	int N,M;

	scanf("%d %d",&N,&M);
	V = M+1;

	double table[NUM][NUM];

	for(int k = 0; k < N; k++){
		table[0][k] = 0;
	}

	for(int i = 1; i <= M; i++){
		for(int k = 0; k < N; k++){
			scanf("%lf",&table[i][k]);
		}
	}

	double naiseki,norm,r,cost;

	for(int from = 0; from <= M; from++){
		for(int to = 1; to <= M; to++){
			if(to == from)continue;

			naiseki = 0;

			for(int i = 0; i < N; i++){
				naiseki += table[from][i]*table[to][i];
			}

			norm = 0;

			for(int i = 0; i < N; i++){
				norm += table[from][i]*table[from][i];
			}

			if(fabs(norm) < EPS){ //入力には0ベクトルもある

				cost = 0;

				for(int i = 0; i < N; i++){
					cost += table[to][i]*table[to][i];
				}
				edge.push_back(Edge(from,to,cost));
				continue;
			}

			r = naiseki/norm;

			cost = 0;

			for(int i = 0; i < N; i++){
				cost += (table[to][i]-r*table[from][i])*(table[to][i]-r*table[from][i]);
			}

			edge.push_back(Edge(from,to,cost));
		}
	}

	printf("%.10lf\n",MCA(0));

	return 0;
}