gets
*d=j=0
$<.map{_1.split.map &:to_i}.sort_by{-_2}.map{|a,b|(i=j+=1).times{d[i]=[d[i]||1e12,d[i-=1]+a+b*i].min}}
p d[$.*2/3]