namespace simplex
{
	int n,m,next[1011];
	//n:varibel m:equation
	double a[11010][1011];
	#define START_POS 1010
	#define INF 210000000000000.0;
	void pivot(int l,int e)
	{
		int t=START_POS;
		double tmp;
		for(int i=0;i<=n;i++)
			if(a[l][i]!=0){next[t]=i;t=i;}
		next[t]=-1;
		tmp=-a[l][e];
		a[l][e]=-1;
		for(int i=next[START_POS];i!=-1;i=next[i])
			a[l][i]/=tmp;
		for(int i=0;i<=m;i++)
		{
			if(a[i][e]==0)continue;
			if(i==l)continue;
			tmp=a[i][e];a[i][e]=0;
			for(int j=next[START_POS];j!=-1;j=next[j])
				a[i][j]+=a[l][j]*tmp;
		}
	}
	double solve()
	{
		while(1)
		{
			long double min=INF;int l=0,e=0;
			for(int i=1;i<=n;i++)
				if(a[0][i]>0){e=i;break;}
			if(e==0)return a[0][0];
			for(int i=1;i<=m;i++)
				if(a[i][e]<0&&a[i][0]<(-a[i][e])*min)
				{min=a[i][0]/(-a[i][e]);l=i;}
			pivot(l,e);
		}
	}
	#undef INF
	#undef START_POS
}