gets
A=$<.map{_1.split.map &:to_i}.sort_by{-_2}
d=0,*[1e12]*M=$.*2/3
A.map{|a,b|eval'd[i]=[d[i],d[i-=1]+a+b*i].min;'*i=M}
p d[M]