Untitled

#include <bits/stdc++.h>
#define fi first
#define se second
#define bit(x, i) ( (( x ) >> ( i ) ) & 1 )
#define mask(i) ((1LL) << (i))
#define all(v) v.begin(), v.end()
#define cook '\n'
#define Task "energy"

using namespace std ;

const int dx[] = {1, 0, -1, 0} ;
const int dy[] = {0, 1, 0, -1} ;
const int mod = 1e9 + 7 ;
const int maxn = 1005 ;

struct Coor {
    int x, y, z, power ;
    Coor ( int _x = 0, int _y = 0, int _z = 0, int _power = 0 ) {
        x = _x; y = _y; z = _z ; power = _power ;
    }
};

int numPoint, numSource ;
Coor pos[maxn] ;

vector<int> type1, type2 ;

void inp() {
    cin >> numPoint >> numSource ;
    for ( int i = 1; i <= numPoint; i++ ) {
        int x, y, z, power; cin >> x >> y >> z >> power ;
        pos[i] = Coor(x, y, z, power) ;

        if ( (x + y + z) & 1 ) type1.push_back(i) ;
            else type2.push_back(i) ;
    }
}

int seen[maxn], interation = 0;
int MatchL[maxn], MatchR[maxn] ;

int dis(int i, int j) {
    return abs(pos[i].x - pos[j].x) + abs(pos[i].y - pos[j].y) + abs(pos[i].z - pos[j].z) ;
}

bool valid(int u, int i, int cur) {
    return ( dis(u, i) == 1 && ( pos[u].power + pos[i].power ) >= cur ) ;
}

bool findOther(int u, int cur) {
    if ( seen[u] == interation ) return false ;
    seen[u] = interation ;

    for ( int i : type2 ) {
        if ( valid(u, i, cur) == true && ( MatchL[i] == -1 || findOther(MatchL[i], cur) == true ) ) {
            MatchL[i] = u ;
            MatchR[u] = i ;
            return true;
        }
    }
    return false ;
}

bool check(int lowest) {
    for ( int i = 1; i <= numPoint; i++ ) MatchL[i] = MatchR[i] = -1 ;
    for ( int u : type1 ) {
        ++interation ;
        findOther(u, lowest) ;
    }

    int cnt_valid = 0 ;
    for ( int i : type1 ) cnt_valid += ( MatchR[i] != -1 ) ;

    if ( cnt_valid > numSource ) return false ;
    for ( int i : type1 ) if ( MatchR[i] == -1 ) {
        if ( pos[i].power >= lowest ) cnt_valid++ ;
        else {
            bool ok = false ;
            for ( int j : type2 )
                if ( valid(i, j, lowest) == true ) {
                    cnt_valid++ ;
                    ok = true ; break ;
                }

            if ( ok == false ) return false ;
        }
    }

    for ( int i : type2 ) if ( MatchL[i] == -1 ) {
        if ( pos[i].power >= lowest ) cnt_valid++ ;
        else {
            bool ok = false ;
            for ( int j : type1 )
                if ( valid(i, j, lowest) == true ) {
                    cnt_valid++ ;
                    ok = true ; break ;
                }

            if ( ok == false ) return false ;
        }
    }

    return cnt_valid <= numSource ;
}

signed main() {
    ios_base::sync_with_stdio(0) ;
    cin.tie(nullptr) ;
    if ( fopen(Task".inp", "r") ) {
        freopen(Task".inp", "r", stdin) ;
        freopen(Task".out", "w", stdout) ;
    }
    inp() ;
    int L = 1, R = 2e9, ans = -1 ;
    while ( R - L >= 0 ) {
        int M = ( R - L ) / 2 + L ;
        if ( check(M) == true ) {
            ans = M ; L = M + 1 ;
        } else R = M - 1 ;
    }
    cout << ans ;
}