(H,W),*AB = $<.map{|ln| ln.split.map(&:to_i) }

F = lambda{|ls|
	h = ls.size
	next ls if H < h

	l,a,b = ls[-1],*AB[h-1]
	l2 = l<a ? l : l<=b ? b+1 : l
	next ls if W < l2

	next F[ls<<l2]
}
G = lambda{|rs,h|
	r,a,b = rs[h],*AB[h-1]
	r2 = b<r ? r : a<=r ? a-1 : r
	rs[h-1] = r2
	next 1<h ? G[rs, h-1] : rs
}

ls1 = F.call [1]
ls1 = G.call ls1,ls1.size-1

ls2 = ls1.dup
ls2[-1] = W
ls2 = G.call ls2,ls2.size-1
ls2 = F.call [ls2[0]]

(1..H).each{|k|
	p [
		ls1[k]&&ls1[k]-ls1[0]+k,
		ls2[k]&&ls2[k]-ls2[0]+k
	].compact.min||-1
}
