АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Хэн нь хурдан гэдэг дээр маргалдсаар байгаа Bessie түүний найз, Elsie хоёр фермийнхээ зам дээр уралдахаар шийджээ.

Хоёр үнээ нэгэн зэрэг нэг цэгээс уралдаанаа эхлүүлнэ. Үнээнүүд өгөгдсөн хугацаандаа өгөгдсөн тогтмол хурдаар явдаг. Жишээ нь Bessie 3 нэгж хугацааг 5 хурдтайгаар туулж болно эсвэл 6 нэгж хугацааг 10 хурдтайгаар туулж байж ч болох юм. Харин Bessie , Elsie хоёрын тус бүрийн нийт туулсан хугацаа ижил байна.

Харин үнээнүүд танаар тэд уралдааны туршид хэдэн удаа тэргүүлэлээ солилцсоныг тоолуулахыг хүсчээ. Тэргүүлэл солилцоно гэдэг нь хоцорч буй үнээ түрүүлж буй үнээний урд нь гарахыг (зэрэгцэхийг тооцохгүй) хэлнэ. Тэдэнд тусална уу.

Input

Эхний мөр: Зайгаар тусгаарлагдсан N болон M бүхэл тоонууд. (1 <= N, M <= 1000)

2-оос (1+N) дүгээр мөр: Мөр болгон Bessie-гийн ямар хурдаар хэдэн нэгж хугацааг туулсаныг илэрхийлэх хоёр бүхэл тоо. Тус бүрдээ 1000-аас хэтрэхгүй.

(2+N)-ээс (1+N+M) дүгээр мөр: Мөр болгон Elsie-гийн ямар хурдаар хэдэн нэгж хугацааг туулсаныг илэрхийлэх хоёр бүхэл тоо. Тус бүрдээ 1000-аас хэтрэхгүй.

Output

Эхний мөр: Уралдааны туршид хэдэн удаа тэргүүлэл солилцсоныг хэвлэ.

Example

Input:

4 3

1 2

4 1

1 1

2 10

2 3

1 2

3 9

Output:

2

Тайлбар:

Elsie t=3 хүртэл тэргүүлж байсан. Үнээнүүд 6 нэгж зайтай байснаас хойш ойртсоор зэрэгцээд 1 нэгж хугацааг туулсан. Тэгээд Bessie тэргүүлж эхэлсэн.

Удалгүй Elsie ахиад тэргүүлэлээ аваад уралдааныг дуустал тэргүүлсэн.

Орчуулсан : УБ 1-р сургууль Б.Мөнх-Оргил