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