#include <iostream>
#include <fstream>
#include <cmath>
#include <bitset>
#include <climits>

using namespace std;

ifstream in("bibel.in");
ofstream out("bibel.out");

pair<int, int> bil[20];
pair<int, int> bilL[20];
int addit[20];
int additT[20];
int am;
int amL;
pair<int, int> last;
int dp[(1<<17)][20];
int mx = 3.4*(1e9)+1;
int MI = 0;

int dist(pair<int, int> a, pair<int, int> b) {
    return ((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}

int hami(bitset<20> &bit, int crr) {

    if(bit.to_ulong() == 0)
        return dist(last, bil[crr]);

    if(dp[bit.to_ulong()][crr] != 0)
        return dp[bit.to_ulong()][crr];

    int mi = mx;

    for(int i = 1; i <= bit.size(); i++) {
        if(bit[i]) {
            bit[i] = 0;
            mi = min(mi, dist(bil[i], bil[crr]) + hami(bit, i));
            bit[i] = 1;
        }
    }

    dp[bit.to_ulong()][crr] = mi;
    return mi;

}

int solve(int J) {

    int mi = mx;

    bitset<20> bit;

    for(int i = 1; i <= am; i++)
        bit[i] = 1;

    int T = 0;
    pair<int, int> temp;

    for(int i = 1; i <= am; i++) {

        for(int I = 0; I < (1<<am); I++) {
            for(int j = 1; j <= am; j++)
                dp[I<<1][j] = 0;
        }

        bit[i] = 0;
        T = hami(bit, i);

        additT[i] = T+addit[J];

        if(T < mi) {
            temp = bil[i];
            mi = T;
        }
        //cout << mi << " " << temp.first << " " << temp.second << '\n';
        bit[i] = 1;

    }

    last = temp;
    return mi;

}

int main() {

    int x,y,z;
    additT[0] = mx;

    while(true) {

        in >> x;

        if(x == 2)
            break;
        if(x == 1) {

            int mi = mx;

            if(amL == 0)
                mi = solve(0);

            for(int j = 1; j <= amL; j++) {
                last = bilL[j];
                int Q = solve(j)+addit[j];
                //additT[j] = Q;
                mi = min(mi, Q);
            }

            out << mi << '\n';
            for(int j = 1; j <= am; j++)
                bilL[j] = bil[j];
            for(int j = 1; j <= am; j++) {
                addit[j] = additT[j];
                additT[j] = mx;
            }
            amL = am;
            am = 0;
            continue;
        }

        in >> y >> z;
        bil[++am] = {y, z};

    }

    return 0;
}