t,k=0,-D=gets[/ .+/].to_i
$<.map{|s|eval"t,k=[t,k-D].max+%d,[k,t-D].max+%d"%s.split}
p [t,k].max