#include <stdio.h>
#include <math.h>

float x[16],y[16];
int v[16],l[16];
int i,j,k,n;

float len(float x,float y) { return sqrt(x*x+y*y); }


float delkaobalu(int k)
{ int i,j,min,firstj;
  float uhj, uhi, uhij, uhmin;
  float l=0;
  if (0 == (k & (k-1))) return 0.0;
  
  min = -1;
  for (i=0; i<n; i++) if (k&1<<i)
  { if (min == -1) min = i;
    else if (y[i] < y[min] || (y[i]==y[min] && x[i]>x[min])) min = i;
  }
  j = min;
  firstj = j;
  uhj = 0;
  
  do
  {
/*    printf("[%d]",j);*/
    
    uhmin = 1e10;    
    for (i=0; i<n; i++) if (i!=j) if (k & 1<<i)
    { uhi = atan2(y[i]-y[j], x[i]-x[j]);
      uhij = uhi - uhj;
      while (uhij < 0) uhij += 2 * 3.1415926;
      if (uhij < uhmin) uhmin=uhij, min=i;
    }
    l += len(y[min]-y[j], x[min]-x[j]);
    j = min;
    uhj = uhmin;
  } while (j != firstj);
  
  return l;
}



int cena(int k)
{ int i,c=0;
  for (i=0; i<n; i++) if (!(k & 1<<i))
    c += v[i];
  return c;
}

int pokacenadelka(int k)
{ int i,ll=0;
  for (i=0; i<n; i++) if (!(k & 1<<i))
    ll += l[i];
  return ll;
}

int main(void)
{ 
  while (scanf("%d", &n), n!=0)
  {
    int i;
    for (i=0; i<n; i++)
    { scanf(" %f %f %d %d", &(x[i]), &(y[i]), &(v[i]), &(l[i]));
    }
    
    int mincena = 1<<30;
    for (k=0; k < (1<<n); k++)
    { if (delkaobalu(k) <= pokacenadelka(k))
        if (cena(k) < mincena) mincena = cena(k);
    }
    printf("The lost value is %d.\n", mincena);
  }
  
  return 0;
}