#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <complex>
#include <cmath>
using namespace std;

#define SIZE(s) int((s).size())
#define REP(i,n) for (int i=0; i<(n); i++)

int N;
int X[20], Y[20], V[20], L[20];

typedef complex<double> point;

point ZERO(0);

double dist(const point &a, const point &b) { return hypot( real(a)-real(b), imag(a)-imag(b) ); }

double cross_product(const point &a, const point &b) { return real(a)*imag(b) - real(b)*imag(a); }

bool countercw(const point &a, const point &b, const point &c) {
  return cross_product( b-a, c-a ) > 1e-7;
}

int signum(double d) { if (d<-1e-7) return -1; if (d>1e-7) return 1; return 0; }

bool compare_arg(const point &a, const point &b) { 
  if (dist(b,ZERO)<1e-7) return false;
  if (dist(a,ZERO)<1e-7) return true;
  int sgnA = signum(imag(a)), sgnB = signum(imag(b));
  if (sgnA == 0) if (signum(real(a))<0) sgnA = 2;
  if (sgnB == 0) if (signum(real(b))<0) sgnB = 2;
  if (sgnA != sgnB) return sgnA < sgnB;
  if (countercw(ZERO,a,b)) return true;
  if (countercw(ZERO,b,a)) return false;
  return dist(ZERO,a) < dist(ZERO,b);
}

double convex_hull(int ostalo) {
  vector< complex<double> > body;
  REP(i,N) if (ostalo & (1<<i)) body.push_back( point(X[i],Y[i]) );
  if (SIZE(body)==0) return 0;
  if (SIZE(body)==1) return 0;
  if (SIZE(body)==2) return dist(body[0],body[1])*2;
  int K = SIZE(body);
  for (int i=1; i<K; i++) {
    if (imag(body[i]) < imag(body[0])) swap( body[i], body[0] );
    if (imag(body[i]) == imag(body[0])) if (real(body[i]) < real(body[0])) swap( body[i], body[0] );
  }
 
  point offset = body[0]; 
  for (int i=0; i<K; i++) body[i] -= offset;  
  sort( body.begin()+1, body.end(), compare_arg );

  int count = 2;
  vector<int> hull(K+2);
  hull[0]=0; hull[1]=1;
  for (int i=2; i<K; i++) {
    while (count >= 2 && !countercw( body[hull[count-2]], body[hull[count-1]], body[i] )) count--;
    hull[ count++ ] = i;
  }

  double res = 0;
  for (int i=0; i<count; i++) res += dist( body[hull[i]], body[hull[(i+1)%count]] );
  return res;
}


int main() {
  while (1) {
    scanf("%d ",&N);
    if (!N) break;
    REP(i,N) scanf("%d %d %d %d ",&X[i],&Y[i],&V[i],&L[i]);
    int best = 987654321;
    REP(pil,1<<N) {
      int ostane = ((1<<N)-1) ^ pil;
      double dlzka = convex_hull(ostane);
      double viem = 0;
      int cena = 0;
      REP(i,N) if (pil & (1<<i)) {
        cena += V[i];
        viem += L[i];
      }
      if (viem >= dlzka - 1e-9) best = min(best,cena);
    }
    printf("The lost value is %d.\n",best);
  } 
}