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

#define OK_FOR_TOP(A,B,C) ((B.x - A.x)*(C.y-B.y)<=(B.y - A.y)*(C.x-B.x))

#define OK_FOR_BOTTOM(A,B,C) ((B.x - A.x)*(C.y-B.y)>=(B.y - A.y)*(C.x-B.x))

struct spoint
{
  int x, y;
};

spoint inpoint[16];
int inpointsCount;
int nopointsCount;

spoint  points[16];
spoint nopoints[16];
int pointsCount = 0;
int ceny[16];
int ploty[16];

int compare(const void * item1, const void * item2)
{
  spoint * p1 = (spoint*) item1;
  spoint * p2 = (spoint *) item2;

  if(p1->x == p2->y)
    return p1->y - p2->y;
    else
    return p1->x - p2->x;
}

spoint resTop[16];
spoint resBtm[16];

  int resTopIdx = 0;
  int resBtmIdx = 0;


void process(void)
{
  qsort(points, pointsCount, sizeof(spoint), compare); 

  resTopIdx = 0;
  resBtmIdx = 0;
  
  if (pointsCount == 0) return;
  int i = 0;
resTop[0] = points[0];
resBtm[0] = points[0];
while((i<pointsCount) && (points[i].x == points[0].x))
{resTop[++resTopIdx] = points[i++]; }
while((i<pointsCount))
{
  while((resTopIdx >0) && !OK_FOR_TOP(resTop[resTopIdx-1], resTop[resTopIdx], points[i]))
  {
    resTopIdx--;  
  }

  resTop[++resTopIdx] = points[i];

  while((resBtmIdx > 0) && !OK_FOR_BOTTOM(resBtm[resBtmIdx-1], resBtm[resBtmIdx], points[i]))
   {
   resBtmIdx--;
   }

   resBtm[++resBtmIdx] = points[i];
   i++;
}
//vypis
}
#define na2(a)  ((a)*(a))

#define euklid(a,b) (sqrt(na2(a.x - b.x)+na2(a.y-b.y)))

double ohodnot()
{
  double delka = 0;
  if (pointsCount <=1)
  return 0;
  spoint minuly = resTop[0];

//printf("top: %d, btm: %d\n", resTopIdx,resBtmIdx);

  for(int i=1; i<resTopIdx; ++i)
  {
    delka += euklid(resTop[i], minuly);
    
  //printf("%f\n", delka);
    minuly = resTop[i];         
  }
  for(int i=resBtmIdx; i>=0; --i)
  {
    delka += euklid(resBtm[i], minuly);

 // printf("%f\n", delka);
    minuly = resBtm[i];  
  }
  return delka;


}
 
int cenakomplet;
int delka_kdispozici;
int nejlepsi_cena;
int nejlepsi_cena_idx;

int main()
{
while (scanf("%d", &inpointsCount) && (inpointsCount != 0)) {
memset(ceny, 0, sizeof(ceny));
memset(ploty, 0, sizeof(ploty));
for (int hnus=0; hnus<inpointsCount; hnus++) {
scanf("%d %d %d %d\n", &inpoint[hnus].x, &inpoint[hnus].y, &ceny[hnus], &ploty[hnus]);
}
nejlepsi_cena = 160000000;
nejlepsi_cena_idx = -1;



for(int i=0; i<(1<<inpointsCount);++i)
{
  pointsCount = 0;
  nopointsCount = 0;
  cenakomplet = 0;
  delka_kdispozici = 0;
  
  int j = i;
  int k = 0;
  for(j = 0; j< inpointsCount; j++)
  {
   int mask = 1<<j;
   if ((i&mask))
   {
     points[pointsCount++] = inpoint[k++];
  //   printf("1");     
   }
   else
   {
	nopoints[nopointsCount++] = inpoint[k];
        cenakomplet += ceny[k];
	delka_kdispozici += ploty[k++];
   }
  }

  //nprintf("\n");
  process();
  double h = ohodnot();
  //printf("%f\n", h);
  //printf(" komplet: %d\n", cenakomplet);

  //printf(" k disopzici: %d\n", delka_kdispozici);
if(h <= delka_kdispozici)
  {
   if(cenakomplet < nejlepsi_cena)
   {
     nejlepsi_cena = cenakomplet; 
   }
  }

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

} return 0;
}