#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define EPS 0.0001

struct tree { double x,y;
              int v,l; } t[16];
int i,j,N;
struct tree T;

int main() {
  int M,minlost,lost,fence;
  int i0,i,j,k,knext;
  double obv;
  scanf("%d",&N);
  while (N) {
    for (i=0; i<N; i++) scanf("%lf %lf %d %d",&t[i].x,&t[i].y,&t[i].v,&t[i].l);
    for (i=0; i<N; i++) for (j=i+1; j<N; j++) {
      if (t[i].x>t[j].x+EPS) {
        T=t[i]; t[i]=t[j]; t[j]=T;
	continue;
        }
      if (t[i].x<t[j].x-EPS) continue;	
      if (t[i].y>t[j].y) {
        T=t[i]; t[i]=t[j]; t[j]=T;
	continue;
        }
      }
    /* for (i=0; i<N; i++) printf("%.0lf %.0lf ",t[i].x,t[i].y); */
    /* printf("\n"); */
    minlost=20*10000;
    for (M=1; M<(1<<N); M++) {
      /* printf("Trying %d\n",M); */
      lost=0; fence=0;
      for (i=0; i<N; i++) if (!(M&(1<<i))) { lost+=t[i].v; fence+=t[i].l; }
      if (lost>=minlost) continue;
      obv=0;
      for (i0=0; i0<N; i0++) if (M&(1<<i0)) break;
      k=i0;
      /* printf("Start %d\n",k); */
      while (1) {
        for (knext=k+1; knext<N; knext++) if (M&(1<<knext)) break;
	if (knext==N) break;
	if (t[k].x!=t[knext].x)
          for (j=knext+1; j<N; j++) if (M&(1<<j)) {
            if (((t[j].y-t[k].y)/(t[j].x-t[k].x))>((t[knext].y-t[k].y)/(t[knext].x-t[k].x))) knext=j;
	    }
        obv+=sqrt((t[knext].x-t[k].x)*(t[knext].x-t[k].x)+(t[knext].y-t[k].y)*(t[knext].y-t[k].y));
	/* printf("Next %d\n",knext); */
        k=knext;
        }
      if (obv>fence+EPS) continue;
      k=i0;
      while (1) {
        for (knext=k+1; knext<N; knext++) if (M&(1<<knext)) break;
	if (knext==N) break;
	if (t[k].x==t[knext].x) {
          for (j=knext+1; j<N; j++) if ((M&(1<<j))&&(t[j].x!=t[k].x)) break;
	  if (j<N) knext=j;
	  }
	if (t[k].x!=t[knext].x)
          for (j=knext+1; j<N; j++) if (M&(1<<j)) {
            if (((t[j].y-t[k].y)/(t[j].x-t[k].x))<((t[knext].y-t[k].y)/(t[knext].x-t[k].x))) knext=j;
	    }
        obv+=sqrt((t[knext].x-t[k].x)*(t[knext].x-t[k].x)+(t[knext].y-t[k].y)*(t[knext].y-t[k].y));
        k=knext;
        }
      if (obv>fence+EPS) continue;
      minlost=lost;
      }
    printf("The lost value is %d.\n",minlost);  
    scanf("%d",&N);
    }
  return 0;
  }