Problem Setter: Md Jahirul Islam Hridoy (MJiH)
Problem tag: Maximum spanning tree, Kruskal’s or Prim’s algorithm, Bit mask
Tutorial: Instead of calculating distances for all pairs of points, use bit masking to consider all possible 2K sign combinations of coordinates. For each combination, track the maximum value and corresponding point to identify critical edges efficiently. This significantly reduces the edges by focusing only on those connecting extreme points. Once the edges are generated, Kruskal’s or Prim’s algorithm will be applied to build the Maximum Spanning Tree.

Time Complexity: O( 2K *N)

#include <bits/stdc++.h>
using namespace std;
#define SC               scanf
#define PF               printf
#define ull              unsigned long long
#define ld               long double
#define F                first
#define S                second
#define pb               push_back
#define sort_a(a)        sort(a.begin(),a.end());
#define sort_d(a)        sort(a.rbegin(),a.rend());
#define READ(f)          freopen(f, "r", stdin)
#define WRITE(f)         freopen(f, "w", stdout)
#define rev(s)           reverse(s.begin(),s.end())
#define P(ok)            cout << (ok ? "YES\n": "NO\n")
#define __Heart__              ios_base :: sync_with_stdio(false); cin.tie(NULL);
#define ll long long
typedef pair< ll , ll>                   PII;
const int MX = 2e5 + 5 ;
ll par[MX], cnt, cost;
struct heart
{
    ll u, v, w , f , s;

};
bool compare(heart a, heart b)
{

    return a.w > b.w ;

}
vector < heart > edge ;
int find_par(ll id)
{
    return (par[id] == id)? id : par[id] = find_par(par[id]) ;
}
ll mst(ll n)
{
    sort(edge.begin(), edge.end(),compare) ;
    cost = 0, cnt = 0 ;
    for(int i = 0 ; i <= n ; i++)
    {
        par[i] = i ;
    }
    for(int i = 0 ; i< edge.size() ; i++)
    {

        ll u = find_par(edge[i].u) ;
        ll v = find_par(edge[i].v) ;
        if(u != v)
        {
            par[u] = v ;
            cost +=edge[i].w ;

        }
    }
    return cost ;
}
void solve()
{
    ll n, d ;
    cin >> n >> d ;
    ll arr[n + 5][d + 5] ;
    for(int i = 0 ; i < n ; i++)
    {
        for(int j = 0 ; j < d ; j++)
        {
            cin >> arr[i][j] ;
        }
    }
    heart dp[35] ;
    for(int i = 0 ; i < 35 ; i++)
    {
        dp[i].f = INT_MIN ;
        dp[i].s = -1 ;
    }
    for(int i = 0 ; i < n ; i++)
    {
        for(int j = 0 ; j < (1 << d) ; j++)
        {
            ll cur_cost = 0 ;
            for(int k = 0 ; k < d ; k++)
            {
                ll bit = (j & (1 << k)) ;
                cur_cost +=  (bit ?  arr[i][k] : -arr[i][k]) ;
            }
            if(cur_cost > dp[j].f)
            {
                dp[j].f = cur_cost ;
                dp[j].s = i ;
            }
        }
    }
    for(int i = 0 ; i < n ; i++)
    {
        for(int j = 0 ; j < (1 << d) ; j++)
        {
            ll cur_cost = 0 ;
            for(int k = 0 ; k < d ; k++)
            {
                int bit = (j & (1 << k)) ;
               cur_cost +=  (bit ?  arr[i][k] : -arr[i][k]) ;
            }
            ll cur = abs(cur_cost - dp[j].f) ;
            if(cur) edge.pb({i , dp[j].s ,cur ,0,0}) ;

        }
    }
   // for(auto it : edge) cout << it.u << " " << it.v << " " << it.w << endl ;

    cout << mst(n)  ;

}
int main()
{
     __Heart__
    // READ("input0.txt") ;
     //WRITE("output0.txt") ;
     int t ; t = 1 ; while(t--) solve() ;
}