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<cmath>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(v) (v).begin(),(v).end()

const double EPS = 1e-8;
typedef double Weight;
const Weight inf = 1LL << 50;

struct Edge {int src, dst; Weight weight;};

struct DMST {
  int N;
  vector< vector<Edge> > g;

  DMST (int n) {
    N = n;
    g.clear();
    g.resize(n);
  }

  vector<int> prev, visited;
  vector<Weight> min_weight;

  // rootツづーツ債ェツづつオツつスツ有ツ古シツ催渉ャツ全ツ暗ヲツ姪伉づーツ仰づ淞づゥ
  // gツづ債破ツ嘉ウツつウツづェツづゥ
  Weight dMST(int root) {

    // ツづ債つカツづ淞づ詠ootツつゥツづァツ全ツ点ツづ可督楪達ツ嘉つ能ツづづ按つ「ツづ按づァreturn inf
    visited.assign(N, 0);
    visited[root] = 1;
    vector<int> S; S.push_back(root);
    while( !S.empty() ) {
        int cur = S.back(); S.pop_back();
        REP(i, g[cur].size()) {
            int next = g[cur][i].dst;
            if( !visited[next] ) {
                visited[next] = 1;
                S.push_back(next);
            }
        }
    }
    if( count(ALL(visited), 1) != N ) return inf;

    Weight total_weight = 0;
    for(;;) {
        prev.assign(N, -1);
        min_weight.assign(N, inf);

        // ツ各ツ陳クツ点ツづ可禿シツづゥツ催渉ャツづ個陛督つセツつッツつゥツづァツづ按づゥツグツδ可フツづーツ催ャツづゥ
        REP(i, N) REP(j, g[i].size()) {
            const Edge &e = g[i][j];
            if( e.dst != root && e.src != e.dst && min_weight[e.dst] > e.weight ) {
                min_weight[e.dst] = e.weight;
                prev[e.dst] = e.src;
            }
        }

        // ツ仰ュツ連ツ個仰青ャツ閉ェツ閉ェツ嘉ーツづサツイツクツδ仰づーツ個淞出
        vector<int> order;
        visited.assign(N, 0);
        REP(i, N) if( !visited[i] && prev[i] != -1 ) dfs(i, order);
        visited.assign(N, -1);
        int scc_num = 0;
        for(int i = order.size() - 1; i >= 0; i--)
            if( visited[order[i]] == -1 )
                rdfs(order[i], scc_num++);

        // ツ適ツ静伉づ可エツッツジツづ個重ツづ敖づーツ更ツ新ツつオツづ按つェツづァツサツイツクツδ仰づーツ縮ツ姪アツつキツづゥ
        bool stop = true;
        REP(scc, scc_num) {
            if( count( ALL(visited), scc) >= 2 ) {
                stop = false;
                // ツ縮ツ姪ア
                int contract = N;
                REP(i, N) if( visited[i] == scc) { contract = i; break; }
                Weight cycle_sum = 0;
                REP(i, N) if( visited[i] == scc) cycle_sum += min_weight[i];

                REP(i, N) REP(j, g[i].size()) {
                    Edge &e = g[i][j];
                    if( visited[e.dst] == scc) e.weight += cycle_sum - min_weight[e.dst];
                    if( visited[e.src] == scc) e.src = contract;
                    if( visited[e.dst] == scc) e.dst = contract;
                }
            }
        }

        if( stop ) {
            REP(i, N) if( prev[i] != -1 ) total_weight += min_weight[i];
            break;
        }
    }
    return total_weight;
  }

  void dfs(int p, vector<int> &order) {
    visited[p] = 1;
    if( prev[p] != -1 && !visited[prev[p]] ) dfs(prev[p], order);
    order.push_back(p);
  }
  void rdfs(int p, int scc) {
    visited[p] = scc;
    REP(i, N) if( prev[i] == p && visited[i] == -1 ) rdfs(i, scc);
  }

  void debug() {
    REP(i, N) {
        cout << i << " : ";
        REP(j, g[i].size()) cout << "(" << g[i][j].src << "->" << g[i][j].dst << " " << g[i][j].weight << ") ";
        cout << endl;
    }
  }
};


int main() {
  int N, M;
  scanf("%d%d", &N, &M);

  vector<double> v[M + 1];
  REP(m, M) {
      REP(n, N) {
          double x; cin >> x;
          v[m].push_back(x);
      }
  }
  v[M] = vector<double>(N, 0.0);

  DMST dmst(M + 1);
  REP(i, M) REP(j, M + 1) if (i != j) {
      double p = 0, q = 0;
      REP(k, N) p += v[i][k] * v[j][k];
      REP(k, N) q += v[j][k] * v[j][k];
      double r = p / q;
      if (abs(q) < EPS) r = 0;
//       cout << i << " " << j << " " << r << endl;
      double w = 0;
      REP(k, N) {
          w += (v[i][k] - v[j][k] * r) * (v[i][k] - v[j][k] * r);
      }
      dmst.g[j].push_back( (Edge){j, i, w} );
  }
//   dmst.debug();

  double ans = dmst.dMST(M);
  printf("%.8f\n", ans);

  return 0;
}