gets
*d=j=0
$<.map{_1.split.map &:to_i}.sort_by{-_2}.map{i=j+=1
d[i]=[d[i]||1e12,d[i-=1]+_1+_2*i].min while i>0}
p d[~j/3]