アミダクジ
＜Description＞
アミダクジ大会が開催されようとしている。
N本の縦線の間に何本もの横線が引かれているアミダクジはすでに完成しており、N人の参加者それぞれが１枚ずつ持っている整理券の番号（重複なし）が、各々の縦線の上に１つずつ記入されている。また、ある縦線の下には当たりを表すハートマークが描かれており、他の縦線の下には何も書かれていない。右端の番号から順にアミダクジを辿っていき、下のハートマークに辿り着くことができた番号の書かれた整理券を持っている１人だけが当たりとなる。
クジ引きの女神であるあなたは、とある名前の分からない高校生から、時間がないので一発でアミダクジの当たりが出るようにしてほしいと頼まれている。つまりあなたは、アミダクジに何本かの横線を書き加えて、右端の縦線の上からアミダクジを辿っていくとハートマークに到達するようにしなければならない。その際、できるだけ目立たないよう、書き加える横線の本数はできるだけ少なくするのが望ましい。
（アミダクジのルールは省略する）
＜input＞
アミダクジを構成する縦線の本数N (2<=N<=1000)、横線の本数M (N<=M<=10000)、ハートマークが書かれている縦線の場所、横線が引かれている場所。
なお、全ての横線は縦線に垂直に、隣り合った縦線同士を結ぶように引かれている。さらに、横線が引かれている場所の高さは、全て異なっていると仮定してよい。
＜output＞
書き加えるべき横線の本数（書き加える必要がないときは0）。
なお、既に横線が引かれている場所と同じ高さに横線を書き加えてはならないものとする。
