D. Ваня ба эрдэнэс

хугацааны хязгаарлалт 1.5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Ваня $n × m$ хэмжээтэй хүснэгтээр дүрслэгдэх нэгэн газар байрлаж байв. Хүснэгтийн өрөө (нүд) бүр нь нэг ширхэг хайрцаг агуулах бөгөөд $i$-дахь мөр болон $j$-дэх баганад байрласан өрөө нь $a_{ij}$ төрлийн хайрцаг агуулж байв. $x ≤ p - 1$ төрлийн хайрцаг болгон нь $x + 1$ төрлийн ямар ч хайрцгийг онгойлгож чадах түлхүүр агуулдаг ажээ. Түүнчлэн $1$-р төрлийн бүх хайрцгууд нь онгорхой байна. Мөн $p$ төрлийн яг ганц хайрцаг оршин байгаа бөгөөд уг хайрцагт эрдэнэс байрлаж байв.

Ваня $(1, 1)$ нүднээс (зүүн дээд булан) хөдөлж эхэлнэ. Тэгвэл Ваня эрдэнэсийг авахын тулд алхах ёстой нийт зайны хамгийн бага утгыг олно уу. $(r_{1}, c_{1})$ ($r_{1}$-р мөр болон $c_{1}$-р баганад байрлах нүд) болон $(r_{2}, c_{2})$ гэсэн нүднүүдийн хоорондох зай нь $|r_{1} - r_{2}| + |c_{1} - c_{2}|$-тай тэнцүү байна.

Оролт

Эхний мөрөнд харгалзан Ваня-ын байгаа газрыг илэрхийлэх хүснэгтийн мөрийн тоо, баганын тоо болон ялгаатай төрлийн хайрцгуудын тоог илэрхийлэх 3 бүхэл тоо $n$, $m$ болон $p$ ($1 ≤ n, m ≤ 300, 1 ≤ p ≤ n*m$) өгөгдөнө.

Дараагийн $n$ мөрийн мөр болгонд $m$ ширхэг бүхэл тоо $a_{ij}$ ($1 ≤ a_{ij} ≤ p$)-ууд өгөгдөх ба эдгээр нь харгалзах өрөөнд байрлах хайрцгийн төрлийг илэрхийлнэ. Мөн $1$-ээс $p$ хүртэлх $x$ бүрийн хувьд дор хаяж нэг ширхэг $x$ төрлийн хайрцаг оршин байх юм. Өөрөөр хэлбэл $a_{rc} = x$ байх $r$ болон $c$-ын хос оршин байна гэсэн үг юм. Мөн түүнчлэн $p$ төрлийн яг нэг ширхэг хайрцаг оршин байна.

Гаралт

$p$ төрлийн хайрцгаас эрдэнэсийг авахын тулд Ваня-ын алхах ёстой нийт алхалтын боломжит хамгийн бага утгыг хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
3 4 3
2 1 1 1
1 1 1 1
2 1 1 3
Гаралт
5
Оролт
3 3 9
1 3 5
8 9 7
4 6 2
Гаралт
22
Оролт
3 4 12
1 2 3 4
8 7 6 5
9 10 11 12
Гаралт
11
Сэтгэгдлүүдийг ачааллаж байна...