S=sorted
E=enumerate
def f(d,p):
 q,M,U,D=[([],p,0)],-1,[],{}
 while q:
  (a,p,c),*q=S(q,key=lambda x:(len(x[1]),x[2]))
  if[]==p:M=[c,min(M,c)][M>-1];continue
  for j,k in E(p):
   for A in[a+[[k]]]+[a[:J]+[K+[k]]+a[J+1:]for J,K in E(a)]:
    if(P:=S(map(S,A)))not in U:
     U+=P,;C=sum(d+sum(j/2for j in i[:len(i)//2])+sum(i[len(i)//2:])for i in P)
     if not(V:=D.get(str(T:=p[:j]+p[j+1:])))or C<=V:q+=(P,p[:j]+p[j+1:],C),;D[str(T)]=C
 return M
 
import re
for i in filter(None, """
6, [20] -> 26
6, [20, 30] -> 46
6, [20, 20] -> 36
12, [20, 2200] -> 2222
6, [20, 30, 40] -> 86
6, [20, 30, 60] -> 106
6, [20, 40, 60] -> 112
6, [20, 30, 40, 50] -> 121
6, [20, 30, 60, 70] -> 152
4, [20, 30, 20, 20, 30] -> 103
4, [30, 30, 20, 20, 30] -> 113
5, [88, 88, 88, 88, 8, 8] -> 286
5, [20, 20, 20, 20, 20, 20, 20] -> 115
100, [10, 20, 10, 20, 10, 20, 10, 20] -> 200
2, [10, 20, 30, 40, 50, 60, 70, 80] -> 288
5, [16, 30, 18, 10, 14, 12, 20, 28] -> 126""".split('\n')):
	*a, b = map(eval, re.split('\s\-\>\s|,\s(?=\[)', i))
	assert f(*a) == b
print('tests passed')

Uz1zb3J0ZWQKRT1lbnVtZXJhdGUKZGVmIGYoZCxwKToKIHEsTSxVLEQ9WyhbXSxwLDApXSwtMSxbXSx7fQogd2hpbGUgcToKICAoYSxwLGMpLCpxPVMocSxrZXk9bGFtYmRhIHg6KGxlbih4WzFdKSx4WzJdKSkKICBpZltdPT1wOk09W2MsbWluKE0sYyldW00+LTFdO2NvbnRpbnVlCiAgZm9yIGosayBpbiBFKHApOgogICBmb3IgQSBpblthK1tba11dXStbYVs6Sl0rW0srW2tdXSthW0orMTpdZm9yIEosSyBpbiBFKGEpXToKICAgIGlmKFA6PVMobWFwKFMsQSkpKW5vdCBpbiBVOgogICAgIFUrPVAsO0M9c3VtKGQrc3VtKGovMmZvciBqIGluIGlbOmxlbihpKS8vMl0pK3N1bShpW2xlbihpKS8vMjpdKWZvciBpIGluIFApCiAgICAgaWYgbm90KFY6PUQuZ2V0KHN0cihUOj1wWzpqXStwW2orMTpdKSkpb3IgQzw9VjpxKz0oUCxwWzpqXStwW2orMTpdLEMpLDtEW3N0cihUKV09QwogcmV0dXJuIE0KIAppbXBvcnQgcmUKZm9yIGkgaW4gZmlsdGVyKE5vbmUsICIiIgo2LCBbMjBdIC0+IDI2CjYsIFsyMCwgMzBdIC0+IDQ2CjYsIFsyMCwgMjBdIC0+IDM2CjEyLCBbMjAsIDIyMDBdIC0+IDIyMjIKNiwgWzIwLCAzMCwgNDBdIC0+IDg2CjYsIFsyMCwgMzAsIDYwXSAtPiAxMDYKNiwgWzIwLCA0MCwgNjBdIC0+IDExMgo2LCBbMjAsIDMwLCA0MCwgNTBdIC0+IDEyMQo2LCBbMjAsIDMwLCA2MCwgNzBdIC0+IDE1Mgo0LCBbMjAsIDMwLCAyMCwgMjAsIDMwXSAtPiAxMDMKNCwgWzMwLCAzMCwgMjAsIDIwLCAzMF0gLT4gMTEzCjUsIFs4OCwgODgsIDg4LCA4OCwgOCwgOF0gLT4gMjg2CjUsIFsyMCwgMjAsIDIwLCAyMCwgMjAsIDIwLCAyMF0gLT4gMTE1CjEwMCwgWzEwLCAyMCwgMTAsIDIwLCAxMCwgMjAsIDEwLCAyMF0gLT4gMjAwCjIsIFsxMCwgMjAsIDMwLCA0MCwgNTAsIDYwLCA3MCwgODBdIC0+IDI4OAo1LCBbMTYsIDMwLCAxOCwgMTAsIDE0LCAxMiwgMjAsIDI4XSAtPiAxMjYiIiIuc3BsaXQoJ1xuJykpOgoJKmEsIGIgPSBtYXAoZXZhbCwgcmUuc3BsaXQoJ1xzXC1cPlxzfCxccyg/PVxbKScsIGkpKQoJYXNzZXJ0IGYoKmEpID09IGIKcHJpbnQoJ3Rlc3RzIHBhc3NlZCcp