TOI9: Spaceship

#include <bits/stdc++.h>
using namespace std;

typedef tuple<int, int, int> tiii;

const int N = 10;

tiii coor[N + 2], piece[N + 2], curr;
bool visited[N + 1];
int nVertex, ans, tr, dist;

int distance(tiii &a, tiii &b){
    int dx = get<0>(a) - get<0>(b);
    int dy = get<1>(a) - get<1>(b);
    int dz = get<2>(a) - get<2>(b);
    return dx * dx + dy * dy + dz * dz;
}

void DFS(int u){
    if(curr == tiii(tr, tr, tr)){
        ans = min(ans, dist);
        return;
    }
    visited[u] = true;
    for(int v = 1; v <= nVertex; ++v){
        if(!visited[v]){
            int dis = distance(coor[u], coor[v]);
            tiii st = curr;
            dist += dis;
            get<0>(curr) = min(tr, get<0>(curr) + get<0>(piece[v]));
            get<1>(curr) = min(tr, get<1>(curr) + get<1>(piece[v]));
            get<2>(curr) = min(tr, get<2>(curr) + get<2>(piece[v]));
            DFS(v);
            dist -= dis;
            curr = st;

        }
    }
    visited[u] = false;
}

int main(){

    tiii st;
    scanf("%d%d%d%d%d", &tr, &get<0>(st), &get<1>(st), &get<2>(st), &nVertex);
    for(int i = 1; i <= nVertex; ++i){
        scanf("%d%d%d%d%d%d", &get<0>(coor[i]), &get<1>(coor[i]), &get<2>(coor[i]), &get<0>(piece[i]), &get<1>(piece[i]), &get<2>(piece[i]));
    }
    coor[nVertex + 1] = st;

    ans = 1e9;
    DFS(nVertex + 1);
    cout << ans;

    return 0;
}