eval'N,_,A='+gets.split*?,
a=(0..N).map{[]}
$<.map{|s|eval'l=%d;a[%d]<<[l-1,%d]'%s.split}
*d=m=A
1.upto(N){|i|m=[m,d[i]=[m-A,*a[i].map{|l,p|d[l]-A+p}].max].max}
p d[N]