/* Author : Harshit Jain a.k.a. iharshit009 */ #include <bits/stdc++.h> #define vi vector<int> #define pb(x) push_back(x) #define int long long #define endl "\n"; #define IOS ios_base::sync_with_stdio(false);cin.tie(0) #define all(x) x.begin(), x.end() #define deb(x) cout << '>' << #x << ':' << x << endl; const int mod = 1e9 + 7; using namespace std; const int N = 200000 + 5; int n; void fuck(){ int d; cin >> n >> d; vector<pair<int,int>>weight; vector<int>planes[n]; for(int i = 0; i<n; i++){ int orgdist = 0; // chanve for(int j = 0; j<d; j++){ int pp; cin >> pp; orgdist += pp*pp; planes[i].pb(pp); } weight.pb(make_pair(orgdist, i)); } sort(all(weight)); // customize it vector<int>pick; int take; vector<int>differ; int last = -1; for(int i = 0; i<weight.size()/2; i++){ if(weight[i].first == weight[n-i-1].first){ last = weight[i].first; take = weight[i].second; differ.pb(weight[i].second); differ.pb(weight[n-1-i].second); continue; } pick.pb(weight[i].second); pick.pb(weight[n-1-i].second); } if(last == -1 && weight.size()&1) pick.pb(weight[weight.size()/2].second); if(last != -1 && weight.size()&1){ differ.pb(take); } int ans = 0; for(int i = 1; i<pick.size(); i++){ for(int j = 0;j<d; j++){ ans += abs(planes[pick[i]][j] - planes[pick[i-1]][j]); } } int taken = pick[pick.size()-1]; int pole; while(differ.size()){ int maxm = 0; for(auto x : differ){ int inter = 0; for(int i = 0; i<d; i++){ inter += abs(planes[taken][i] - planes[x][i]); } if(maxm < inter){ pole = x; } maxm = max(maxm,inter); } taken = pole; ans += maxm; differ.erase(remove(differ.begin(),differ.end(), pole), differ.end()); } cout << ans << endl; return; } int32_t main(){ IOS; #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int t = 1; // cin >>t; while(t--){ fuck(); // Easy things to check: // - LONG LONGS (WA) // - const int N is correct (WA, RTE) // - .size()-k underflow (WA, RTE, TLE) // - small n edge cases (WA) // Rare mistakes made in the past: // - division by 0 (WA) // - integer division (WA) // - setprecision (WA) // - INF not big enough using ll (WA) // - setting min to 0 instead of -INF (WA) // - outputting debug (WA) // - allocating too much memory (locRTE, MLE) // - stack size (locRTE) } return 0; }