#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
#include <sstream>
#include <complex>
#include <numeric>
#include <bitset>
using namespace std;

#define REP(i,n) for (int i=0; i<int(n); i++)
#define FOR(i,a,n) for (int i=a; i<int(n); i++)
#define FORD(i,n) for (int i=int(n)-1; i>=0; i--)
#define pb push_back
#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> PI;
typedef complex<ll> bod;
ll vs(const bod &a, const bod &b)
{
    return imag(conj(a) * b);
}
ll ss(const bod &a, const bod &b)
{
    return real(conj(a) * b);
}
ll vs(const bod &a, const bod &b, const bod &c)
{
    return vs(c - b, b - a);
}
double jeden(vector<bod> &b)
{
    vector<bod> z;
    for (int i = 0; i < (int)b.size(); i++)
    {
	while (z.size() >= 2 && vs(z[z.size() - 2], z.back(), b[i]) <= 0)
	    z.pop_back();
	z.push_back(b[i]);
    }
    double res = 0;
    REP(i,int(z.size())-1)
	res += sqrt(ss(z[i + 1] - z[i], z[i + 1] - z[i]));
    return res;
}
double zrataj(vector<PI> a)
{
    sort(a.begin(), a.end());
    vector<bod> e(a.size());
    REP(i,a.size()) e[i] = bod(a[i].first, a[i].second);
    double res = jeden(e);
    reverse(e.begin(), e.end());
    return res + jeden(e);
}
int main()
{
    int n;
    while (scanf("%d", &n) == 1)
    {
	if (!n) break;
        vector<PI> a(n);
	vector<int> v(n), l(n);
	REP(i,n) scanf("%d %d %d %d", &a[i].first, &a[i].second, &v[i], &l[i]);

	int ss = 1 << n;
	int res = accumulate(v.begin(), v.end(), 0);
	REP(k,ss)
	{
	    bitset<16> b(k);
	    int viem = 0, hodnota = 0;
	    vector<PI> c;
	    REP(i,n)
	    {
		if (b[i])
		    c.push_back(a[i]);
		else
		{
		    viem += l[i];
		    hodnota += v[i];
		}
	    }
	    if (hodnota < res)
		if (viem >= zrataj(c))
		    res = hodnota;
	}
	cout << "The lost value is " << res << ".\n";
    }
}