PROGRAMING PROBLEMS

Говьд байгуулсан Шинэ Вегас хотын гудамжнууд нь 100 м-ийн урттай тал бүхий квадрат байшингууд болон тэдгээрийн хоорондох гудамжнуудаас тогтоно.

Казиногийн захирал хотын баруун урд буланд оршдог ба зүүн хойд буланд байдаг ажил руугаа өдөр бүр алхдаг.
Захирал үргэлж гудамжаар зүүн тийш эсвэл, хойшоогоо явдаг. Зарим байшингууд доогуураа баруун урдаас зүүн хойш чиглэсэн диаметрийнхээ дагуу арктай ба түүгээр алхах боломжтой.
Түүнд хамгийн богино замын уртыг олоход тусал.
Оролт
Эхний мөрөнд баруунаас зүүн тийш хэдэн эгнээ байшин байгааг илэрхийлэх N тоо болон урдаас хойшоо чиглэлд хэдэн эгнээ байшин байгааг илэрхийлэх M тоо өгөгдөнө (0 < N, M ≤ 1000).
Хоёр дахь мөрөнд доогуураа диагональ арк бүхий байшингуудын тоог илэрхийлэх K бүхэл тоо өгөгдөнө(1 ≤ K ≤ 100).
Дараагийн мөрүүдэд арк бүхий байшингуудын байрлал болох хос эерэг бүхэл тоонууд өгөгдөнө.
Эхний тоо нь байшингийн байрлаж буй баганын дугаар ба баганууд зүүнээс баруун тийш 1-ээс эхлэн дугаарлагдана. Хоёр дахь тоо нь байшингийн байрлаж байгаа мөрийн дугаар ба мөрүүд доороос дээш 1-ээс эхлэн дугаарлагдана.
Гаралт 
Хамгийн богино замыг бүхэл тоо хүртэл тоймлож хэвлэнэ.
Жишээ




Оролт


Гаралт




3 2
3
1 1
3 2
1 2


383