Problem: There are N cities in a two-dimensional plane. The coordinates of the i-th city is (x_i, y_i). Initially, the amount of water stored in the i-th city is a_i liters.

Snuke can carry any amount of water from a city to another city. However, water leaks out a bit while he carries it. If he carries l liters of water from the s-th city to the t-th city, only max(l-d_{s,t}, 0) liters of water remains when he arrives at the destination. Here d_{s,t} denotes the (Euclidean) distance between the s-th city and the t-th city. He can perform arbitrary number of operations of this type.

Snuke wants to maximize the minimum amount of water among the N cities. Find the maximum X such that he can distribute at least X liters of water to each city.

Constraints

* 1 ≤ N ≤ 15
* 0 ≤ x_i, y_i, a_i ≤ 10^9
* All values in the input are integers.
* No two cities are at the same position.

Input

The input is given from Standard Input in the following format:


N
x_1 y_1 a_1
:
x_N y_N a_N


Output

Print the maximum of the minimum amount of water among the N cities. The absolute error or the relative error must be at most 10^{-9}.

Examples

Input

3
0 0 10
2 0 5
0 5 8


Output

6.500000000000


Input

15
335279264 849598327 822889311
446755913 526239859 548830120
181424399 715477619 342858071
625711486 448565595 480845266
647639160 467825612 449656269
160714711 336869678 545923679
61020590 573085537 816372580
626006012 389312924 135599877
547865075 511429216 605997004
561330066 539239436 921749002
650693494 63219754 786119025
849028504 632532642 655702582
285323416 611583586 211428413
990607689 590857173 393671555
560686330 679513171 501983447


Output

434666178.237122833729

Solution (in CPP):

Solution:
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<utility>
#include<functional>
#include<iomanip>
#include<sstream>
#include<ctime>
#include<cassert>
using namespace std;
#define y0 y0z
#define y1 y1z
#define yn ynz
#define j0 j0z
#define j1 j1z
#define jn jnz
#define tm tmz
#define buli(x) (__builtin_popcountll(x))
#define bur0(x) (__builtin_ctzll(x))
#define bul2(x) (63-__builtin_clzll(x))
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fil(a,b) memset((a),(b),sizeof(a))
#define cl(a) fil(a,0)
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define foreach(it,a) for(__typeof((a).begin()) it=(a).begin();it!=(a).end();it++)
#define rep(i,a,b) for (int i=(a),_ed=(b);i<_ed;i++)
#define per(i,a,b) for (int i=(b)-1,_ed=(a);i>=_ed;i--)
#define forg(i,gu) for (int i=gu;~i;i=e[i].next)
#define pw(x) ((ll(1))<<(x))
#define upmo(a,b) (((a)=((a)+(b))%mo)<0?(a)+=mo:(a))
#define mmo(a,b) (((a)=1ll*(a)*(b)%mo)<0?(a)+=mo:(a))
void getre(){int x=0;printf("%d\n",1/x);}
void gettle(){int res=1;while(1)res<<=1;printf("%d\n",res);}
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
template<typename T,typename S>inline bool upmin(T&a,const S&b){return a>b?a=b,1:0;}
template<typename T,typename S>inline bool upmax(T&a,const S&b){return a<b?a=b,1:0;}
template<typename N,typename PN>inline N flo(N a,PN b){return a>=0?a/b:-((-a-1)/b)-1;}
template<typename N,typename PN>inline N cei(N a,PN b){return a>0?(a-1)/b+1:-(-a/b);}
template<typename N>N gcd(N a,N b){return b?gcd(b,a%b):a;}
template<typename N>inline int sgn(N a){return a>0?1:(a<0?-1:0);}
#if ( ( _WIN32 || __WIN32__ ) && __cplusplus < 201103L)
#define lld "%I64d"
#else
#define lld "%lld"
#endif
inline void gn(long long&x){
	int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');c=='-'?(sg=-1,x=0):(x=c-'0');
	while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';x*=sg;
}
inline void gn(int&x){long long t;gn(t);x=t;}
inline void gn(unsigned long long&x){long long t;gn(t);x=t;}
inline void gn(double&x){double t;scanf("%lf",&t);x=t;}
inline void gn(long double&x){double t;scanf("%lf",&t);x=t;}
inline void gs(char *s){scanf("%s",s);}
inline void gc(char &c){while((c=getchar())>126 || c<33);}
inline void pc(char c){putchar(c);}
#ifdef JCVB
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif
typedef long long ll;
typedef double db;
inline ll sqr(ll a){return a*a;}
inline db sqrf(db a){return a*a;}
const int inf=0x3f3f3f3f;
const db pi=3.14159265358979323846264338327950288L;
const db eps=1e-6;
//const int mo=0;
//int qp(int a,ll b){int n=1;do{if(b&1)n=1ll*n*a%mo;a=1ll*a*a%mo;}while(b>>=1);return n;}

int n;

struct pkt{
	int x,y;
	void read(){gn(x);gn(y);}
	ll dissq(){return 1ll*x*x+1ll*y*y;}
	friend pkt operator+(const pkt&a,const pkt&b){return (pkt){a.x+b.x,a.y+b.y};}
	friend pkt operator-(const pkt&a,const pkt&b){return (pkt){a.x-b.x,a.y-b.y};}
	friend pkt operator-(const pkt&a){return (pkt){-a.x,-a.y};}
	friend ll dot(const pkt&a,const pkt&b){return 1ll*a.x*b.x+1ll*a.y*b.y;}
	friend ll cro(const pkt&a,const pkt&b){return 1ll*a.x*b.y-1ll*a.y*b.x;}
	friend bool operator<(const pkt&a,const pkt&b){return a.y==b.y?a.x<b.x:a.y<b.y;}
	/*friend bool operator<(const pkt&a,const pkt&b){
		int aa=a.y>0 || a.y==0&& a.x>0;
		int bb=b.y>0 || b.y==0&& b.x>0;
		if(aa!=bb)return aa<bb;
		else return cro(a,b)>0;
	}*/
}p[15];


db mst[1<<15];

int fa[15];
int gf(int x){
	return x==fa[x]?x:fa[x]=gf(fa[x]);
}
bool un(int u,int v){
	u=gf(u);v=gf(v);
	if(u!=v){
		fa[u]=v;
		return 1;
	}
	return 0;
}
struct edg{
	int u,v;
	db x;
}ee[1111];
int cmp(const edg&a,const edg&b){
	return a.x<b.x;
}
int etot;

db gao(int b){
	etot=0;
	rep(i,0,n)fa[i]=i;
	rep(i,0,n)if(pw(i)&b)rep(j,i+1,n)if(pw(j)&b){
		ee[++etot]=(edg){i,j,sqrt((p[i]-p[j]).dissq())};
	}
	sort(ee+1,ee+1+etot,cmp);
	db su=0.0;
	rep(i,1,etot+1){
		if(un(ee[i].u,ee[i].v))su+=ee[i].x;
	}
	return su;
}
db ini[15];

db f[1<<15];
int main()
{
#ifdef JCVB
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	int _time_jc=clock();
#endif
	gn(n);
	rep(i,0,n){
		p[i].read();
		gn(ini[i]);
	}
	
	rep(b,1,pw(n)){
		mst[b]=gao(b);
	}
	rep(b,1,pw(n)){
		db mia=1e18;
		db su=0.0;
		int cnt=0;
		rep(i,0,n)if(pw(i)&b){
			upmin(mia,ini[i]);
			su+=ini[i];
			cnt++;
		}
		f[b]=mia;

		su-=mst[b];
		upmax(su,0.0);
		su/=cnt;
		upmax(f[b],su);
	}

	f[0]=0.0;
	rep(b,1,pw(n)){
		for (int x=b;x;x=(x-1)&b){
			upmax(f[b],min(f[x],f[b^x]));
		}
	}
	printf("%.10lf\n",f[pw(n)-1]);


#ifdef JCVB
	debug("time: %d\n",int(clock()-_time_jc));
#endif
	return 0;
}