*d=j=0
`read;sort -nrk2`.lines{i=j+=1
eval'd[i]=[d[i]||1e12,d[i-=1]+%s+%s*i].min while i>0'%_1.split}
p d[-~j*2/3]