Диагональ

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

Казиногийн захирал хотын баруун урд буланд оршдог ба зүүн хойд буланд байдаг ажил руугаа өдөр бүр алхдаг.

Захирал үргэлж гудамжаар зүүн тийш эсвэл, хойшоогоо явдаг. Зарим байшингууд доогуураа баруун урдаас зүүн хойш чиглэсэн диаметрийнхээ дагуу арктай ба түүгээр алхах боломжтой.

Түүнд хамгийн богино замын уртыг олоход тусал.

Оролт

Эхний мөрөнд баруунаас зүүн тийш хэдэн эгнээ байшин байгааг илэрхийлэх N тоо болон урдаас хойшоо чиглэлд хэдэн эгнээ байшин байгааг илэрхийлэх M тоо өгөгдөнө (0 < N, M ≤ 1000).

Хоёр дахь мөрөнд доогуураа диагональ арк бүхий байшингуудын тоог илэрхийлэх K бүхэл тоо өгөгдөнө(1 ≤ K ≤ 100).

Дараагийн мөрүүдэд арк бүхий байшингуудын байрлал болох хос эерэг бүхэл тоонууд өгөгдөнө.

Эхний тоо нь байшингийн байрлаж буй баганын дугаар ба баганууд зүүнээс баруун тийш 1-ээс эхлэн дугаарлагдана. Хоёр дахь тоо нь байшингийн байрлаж байгаа мөрийн дугаар ба мөрүүд доороос дээш 1-ээс эхлэн дугаарлагдана.

Гаралт

Хамгийн богино замыг бүхэл тоо хүртэл тоймлож хэвлэнэ.

Жишээ

Оролт	Гаралт
3 2 3 1 1 3 2 1 2	383

Блок

Бодлогын нэр: Блок

Хугацаа: 1 сек

Бат Болд хоёр блокоор байшин барьж тоглож байгаа ба ингэхдээ тэр хоёр хоёулаа тус тусдаа сондгой тооны N ширхэг байшин цувуулан барив. Батын барьж байгаа байшингуудыг эхнээс нь m_i гэж дугаарлаад мөн Болдын байшингуудыг s_i гэж дугаарлая (1 <= i <= N).

            Тэр хоёр өөрсдийн барьсан байшингуудаа бүгдийг нь харгалзан s_i болон m_iнь тэнцүү өндөртэй болгохоор шийдэв. Ингэхдээ дараах дүрмийг барина:

            Байшингуудын зүүн талаас эхлэх ба эхлээд бүх байшингуудын өндрүүдийг эрс буурах байдлаар болгоод хамгийн голын байшин хүрсний дараа дараачийн байшингуудын өндрийг эрс өсөх байдлаар өөрчлөхөөр болов. Ингэхдээ мөн дурын дараалсан хоёр байшингийн өндрийн зөрөөг 1 байлгана. Доорх зургаас тодорхой харна уу.

  

           

Ямар нэгэн байшингийн өндрийг өөрчлөхдөө тухайн байшингийн дээрээс нь нэг блок аваад хаяж болно (үүнийгээ дахин ашиглахгүй) эсвэл уутнаас шинэ блок гаргаж тухайн байшингийн дээр нь давхарлаж тавих гэсэн 2 үйлдэл зөвшөөрөгдсөн (саванд хангалттай тооны блок байгаа гэж үз).

            Таны даалгавар бол Бат Болд хоёрын тус тусдаа барьсан байшингуудын өндрүүд өгөгдсөн (хамгийн зүүн талаасаа) бол дээр дурьдсан байдлаар байшингуудаа өөржлөхөд хийгдэх хамгийн бага үйлдлийн тоог олох явдал юм.

           

Оролт:

Оролтын файлын эхний мөрөнд сондгой N (1 <= N <= 300 000) буюу Бат Болд хоёрын тус тусдаа барьж буй байшингуудын тоо.

Дараачийн хоёр мөрт тус бүр N тоо байх ба энэ нь эхлээд Батын барьсан байшингуудын өндрүүд зүүн талаасаа эхлэн өгөгдөнө m_i. Дараа нь Болдын барьсан байшингуудын өндрүүд мөн зүүн талаасаа эхлэн өгөгдөнө s_i.

(0 <= m_i<= 10¹²) (0 <= s_i<= 10¹²).

Гаралт:

Бодлогын хариу болох ганц тоо.

Жишээнүүд:

Оролт	Оролт
3 1 2 3 3 2 2	5 2 3 0 1 4 3 3 2 3 1
Гаралт	Гаралт
3	10

Тайлбар:

1-р жишээн дээр Бат эхний байшин дээрээ 2 блок тавина харин Болд 3 дахь байшин дээрээ нэг блок тавихад адилхан болно.