def opt(basis,cols):
 while True:
  I,x,pi=binfo(basis)
  ids=set(c['cid'] for c in basis)
  best=None
  for c in cols:
   if c['cid'] in ids: continue
   rc=c['cost']-sum(pi[i]*c['cov'][i] for i in range(7))
   if rc<0 and (best is None or rc<best[0] or (rc==best[0] and c['cid']<best[1]['cid'])): best=(rc,c)
  if best is None: return basis,x,pi
  c=best[1]
  d=[sum(I[i][j]*c['cov'][j] for j in range(7)) for i in range(7)]
  rp=None
  for p in range(7):
   if d[p]>0:
    rat=x[p]/d[p]
    if rp is None or rat<rp[0] or (rat==rp[0] and p<rp[1]): rp=(rat,p)
  if rp is None: raise Exception('unb')
  basis[rp[1]]=c