#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

typedef struct TREE
{
    int X,Y,L,V;
} tree;

typedef struct POINT
{
    int x,y;
} point;

point p[18];
point o[40];
int np,no;

int ccw(point a, point b, point c)
{
    return (c.x-a.x) * (c.y-b.y) - 
           (c.x-b.x) * (c.y-a.y);
}

#define sqr(a) ((a)*(a))

void insert(int i) {
    while (no>=2 && ccw(o[no-2],o[no-1],p[i]) < 0)
        no--;

    o[no++]=p[i];
}
void hull() {
    if (np==1) return;
    if (np==2) {
        o[0]=p[0];
        o[1]=p[1];
        no=2;
        return;
    }

    int i;
    o[0]=p[0]; o[1]=p[1];
    no=2;
    for (i=2;i<np;i++)
        insert(i);
    for (i=np-2;i>=0;i--)
        insert(i);
}

bool cmp(point a, point b) {
    if (a.x==b.x) return a.y < b.y;

    return a.x < b.x;
}
    
void sortp() {
    sort(p,p+np,cmp);
}

double fencelength() {
    if (np==1) return 0;
    double len;
    for (int i=1;i<no;i++) {
        len+=sqrt(sqr(o[i-1].x-o[i].x)+sqr(o[i-1].y-o[i].y));
    }
    len+=sqrt(sqr(o[no-1].x-o[0].x)+sqr(o[no-1].y-o[0].y));

   return len;
}

int pw(int N) {
    int ret=1;
    while (N--) {
        ret*=2;
    }

    return ret;
}

int main() {
    int N;
    while (scanf("%d",&N),N) {
        tree t[18];
        for (int i=0;i<N;i++){
            scanf("%d %d %d %d",&t[i].X,&t[i].Y,&t[i].V,&t[i].L);
        }

        int pow=pw(N);
        int minlost=0;
        bool first=true;
        for (int i=0;i<pow;i++) {
            int canlength=0;
            int lostvalue=0;

            np=0;
            int bitp=i; 
            for (int j=0;j<N;j++) {
                if (bitp&1) {
                    p[np].x=t[j].X;
                    p[np++].y=t[j].Y;
                } else {
                    canlength+=t[j].L;
                    lostvalue+=t[j].V;
                }
                bitp= bitp>>1;
            }

            sortp();

            hull();
            double tmp=fencelength();
            if (tmp<=canlength) {
                if (first) minlost = lostvalue; else if (lostvalue<minlost) minlost=lostvalue;
                first=false;
            }
        }

        printf("The lost value is %d.\n",minlost);
        
        
    }

    return 0;
}