#include<stdio.h> 
#include<string.h> 
#define MAX 100 
#define infinity 100000000 
double c[MAX]; 
double g[MAX][MAX]; 
int B[MAX],mark[MAX]; 
// g[0] presents b; 
// g[0] presents r; 
int m,n; 
int readdata() 
{ 
int x,y; 
memset(c,0,sizeof?); 
memset(g,0,sizeof(g)); 
memset(mark,0,sizeof(mark)); 
scanf("%d %d",&n,&m); 
for(y=1;y<=n;y++)scanf("%lf",&c[y]); 

for(x=1;x<=m;x++) 
{ 
scanf("%d",&B[x]); 
for(y=1;y<=n;y++) 
scanf("%lf",&g[x][y]); 
scanf("%lf",&g[x][0]); 
} 
return 0; 
} 
int initial() 
{ 
int x,y; 
for(x=1;x<=m;x++){mark[B[x]]=1;} 
for(x=1;x<=n;x++) 
if(!mark[x]) 
{ 

g[0][x]=c[x];for(y=1;y<=m;y++)g[0][x]-=c[B[y]]*g[y][x];//r=c-Cb*B^( 
-1)*P 
} 
for(x=1;x<=m;x++)g[0][0]+=c[B[x]]*g[x][0]; 
g[0][0]=-g[0][0]; 
return 0; 
} 
int guass(int a,int 
{ 
int x,y; 
double mainelem,colelem; 
mainelem=g[a]; 
for(x=0;x<=n;x++)g[a][x]/=mainelem; 
for(x=0;x<=m;x++) 
{ 
colelem=g[x]; 
if(x!=a)for(y=0;y<=n;y++) 
{ 
g[x][y]-=colelem*g[a][y]; 
} 
} 
return 0; 
} 
int print(int a,int 
{ 
int x,y; 
printf("-----------\n"); 
for(x=1;x<=m;x++) 
{ 
printf("x%3d :",B[x]); 
for(y=1;y<=n;y++) 
{ 
if(x==a&&y== printf("[%6.3lf]",g[x][y]); 
else printf("%7.3lf ",g[x][y]); 
} 
printf("| %5.1lf\n",g[x][0]); 
} 
printf("criti:"); 
for(x=1;x<=n;x++)printf("%7.3lf ",g[0][x]); 
printf("| %7.3lf\n",g[0][0]); 
return 0; 
} 
int calc_max() 
{ 
int x,y,i,j; 
double max;int maxnum; 
double min;int minnum; 
int find; 

while(1) 
{ 
max=-infinity; 
for(x=1;x<=n;x++)if(g[0][x]>max){max=g[0][x];maxnum=x;}//find 
the max crit 
erion 
if(max<=0) 
{ 
print(0,0); 
printf("the optimal solution is :%lf.\n",-g[0][0]); 
return 0; 
}else//col[mmnum]is the main col 
{ 
find=0;min=infinity; 
for(y=1;y<=m;y++) 
{ 
if(g[y][maxnum]>0){ 
find=1; 

if(g[y][0]/g[y][maxnum]<min){min=g[y][0]/g[y][maxnum];minnum=y;} 

} 
} 
if(!find){printf("no optimal solution!\n");return 0;} 
mark[B[minnum]]=0;mark[maxnum]=1; 
B[minnum]=maxnum;//the X[maxnum] enter the Base ,the 
B[minnum] quit the B 
ase; 
print(minnum,maxnum); 
guass(minnum,maxnum); 
} 
} 
return 0; 
} 
int main() 
{ 
freopen("sim.in","r",stdin); 
freopen("sim.out","w",stdout); 
readdata(); 
initial(); 
calc_max(); 
fclose(stdin); 
fclose(stdout); 
return 0; 
}