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 <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const double INF = 1e32;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
struct Edge{
  int src, dst;
  double cost;
  Edge(int s, int d, double c) : 
    src(s), dst(d), cost(c) {}
};
typedef vector<Edge> Node;
typedef vector<Node> Graph;
void add_edge(Graph& G, int a, int b, double c){
  G[a].push_back(Edge(a, b, c));
}
// Strongly Connected Components(強連結成分)

// Step1
void SCC_dfs(const Graph& G, vector<bool>& visit, vector<int>& order, int v){
  visit[v] = true;
  REP(i, G[v].size()){
    int dst = G[v][i].dst;
    if(!visit[dst]) SCC_dfs(G, visit, order, dst);
  }
  order.push_back(v);
}

// Step2
Graph reverse_graph(const Graph& G){
  Graph revG(G.size());
  REP(i, G.size()){
    REP(j, G[i].size()){
      const Edge &e = G[i][j];
      revG[e.dst].push_back(Edge(e.dst, e.src, e.cost));
    }
  }
  return revG;
}

// Step3
void SCC_rdfs(const Graph& G, vector<bool>& visit, vector<int>& comp, int v, int k){
  visit[v] = true;
  REP(i, G[v].size()){
    int dst = G[v][i].dst;
    if(!visit[dst]) SCC_rdfs(G, visit, comp, dst, k);
  }
  comp[v] = k;
}

// 強連結成分分解
int SCC(const Graph& G, vector<int>& comp){
  Graph revG = reverse_graph(G);
  comp = vector<int>(G.size());
  vector<bool> visit(G.size());
  vector<int> order(G.size());
  int k = 0;
  REP(i, G.size()) if(!visit[i]) SCC_dfs(G, visit, order, i);
  reverse(order.begin(), order.end()); 

  visit = vector<bool>(G.size());
  REP(i, order.size()){
    if(!visit[order[i]]) SCC_rdfs(revG, visit, comp, order[i], k++);
  }
  return k;
}


double MOB(Graph& G, int root){
  int V = G.size();
  double res = 0;

  // 各ノードに入る最小の辺を求める
  vector<Edge> min_edge(V, Edge(-1, -1, INF));
  REP(v, V) REP(i, G[v].size()){
    Edge& e = G[v][i];
    if(min_edge[e.dst].cost > e.cost){
      min_edge[e.dst] = e;
    }
  }

  // コストを足し合わせる
  /*
  printf("V = %d root = %d\n", V, root);
  REP(v, V) REP(i, G[v].size()) printf("G[%d][%d] = Edge(%d, %d, %lf)\n", v, i, G[v][i].src, G[v][i].dst, G[v][i].cost);
  REP(v, V) printf("min_edge[%d].cost = %lf\n", v, min_edge[v].cost);
  */
  REP(v, V) if(v != root) {
    if(min_edge[v].cost == INF) return INF; // rootから到達不可能な頂点が存在する
    res += min_edge[v].cost;
  }

  // 各辺のコストを、最小のコスト分だけ減らす
  REP(v, V) REP(i, G[v].size()){
    Edge& e = G[v][i];
    if(e.dst != root) e.cost -= min_edge[e.dst].cost;
  }

  // 強連結成分分解で、ループがあるかどうか調べる
  Graph sG(V);
  REP(v, V) if(v != root) {
    Edge& e = min_edge[v];
    sG[e.src].push_back(e);
  }
  vector<int> comp;
  int m = SCC(sG, comp);
  if(m == V) return res; // ループがなければ終了

  // 次に調べるグラフを作る
  Graph nG(m);
  REP(v, V) REP(i, G[v].size()){
    Edge& e = G[v][i];
    if(comp[v] != comp[e.dst]) nG[comp[v]].push_back(Edge(comp[v], comp[e.dst], e.cost));
  }

  return min(INF, res + MOB(nG, comp[root]));
}
int main(){
  int N, M;
  while(cin >> N >> M){
    vector<double> v[100];
    REP(i, M){
      v[i] = vector<double>(N);
      REP(j, N) cin >> v[i][j];
    }
    double dot[100][100] = {};
    REP(i, M) REP(j, M){
      REP(k, N) dot[i][j] += v[i][k] * v[j][k];
    }
    double dist[100][100] = {};
    REP(i, M) REP(j, M){
      dist[i][j] = dot[j][j] - (abs(dot[i][i]) < 1e-9 ? 0.0 : (dot[i][j] * dot[i][j]) / dot[i][i]);
    }
    Graph G(M + 1);
    REP(i, M) REP(j, M) if(i != j) {
      add_edge(G, i, j, dist[i][j]);
    }
    REP(i, M) {
      add_edge(G, M, i, dot[i][i]);
    }
    printf("%.16lf\n", MOB(G, M));
    //REP(i, M) REP(j, M) printf("dist[%d][%d] = %lf\n", i, j, dist[i][j]);
    /*
    double ans = 1e16;
    REP(s, M){
      typedef pair<double, double> P;
      typedef pair<P, int> S;
      priority_queue<S, vector<S>, greater<S> > que;
      que.push(S(P(dot[s][s], dot[s][s]), s));
      double used[100] = {};
      double sum = 0;
      //printf("start = %d\n", s);
      while(!que.empty()){
        double alld = que.top().first.first;
        double d = que.top().first.second;
        int u = que.top().second;
        //printf("alld = %lf d = %lf u = %d\n", alld, d, u);
        que.pop();
        if(used[u]) continue;
        //printf("add %d %lf\n", u, d);
        sum += d;
        used[u] = true;
        REP(i, M) if(!used[i]){
          //printf("push(%lf, %lf, %d)\n", alld + dist[u][i], dist[u][i], i);
          que.push(S(P(alld + dist[u][i], dist[u][i]), i));
        }
      }
      //printf("sum = %lf\n", sum);
      ans = min(ans, sum);
    }
    printf("%.16lf\n", ans);
    */
  }
  return 0;
}