*d=s=0
gets.to_i.times{eval'A,B='+gets.split*?,
s+=B
(10**5).downto(A){|i|d[i]=[d[i]||0,(d[i-A]||0)+B].max}}
i=-1
p d.map{|d|[i+=1,s-(d||0)].max}.min