D. Игор Музейд

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

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

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

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

Игор музейд байгаа ба боломжит хамгийн их зураг үзэхийг хүсч байна.

Музей $n × m$ нүдтэй тэгш өнцөгт хэлбэрээр дүрслэгдэж чадна. Нүд бүр хоосон эсвэл битүү байна. хоосон нүднүүд '$.$'-р тэмдэглэгдэх бол битүү нүднүүд '$*$'-р тэмдэглэгдэнэ. Ялгаатай төрлийн (нэг нь хоосон нэг нь битүү) хоёр хөрш нүд бүр нэг зураг агуулсан ханаар хуваагдана.

Эхлээд Игор нэг хоосон нүдэнд байна. Мөч бүрт тэр өөрийн байгаа нүдтэй нэг талаа хуваалцсан дурын хоосон нүдрүү очиж чадна.

Хэд хэдэн эхлэлийн байрлалын хувьд та Игорийн үзэж чадах зургийн хамгийн их тоог тооцоолох ёстой. Игор уг зурагтай ханын хөрш нүдэнд байвал л уг зургийг харах боломжтой. Игор маш завтай явж байгаа ба өөрийн үзэж чадах бүх зургийг судлана.

Оролт

Оролтын эхний мөрөнд гурван бүхэл тоон утга $n$, $m$ ба $k$ ($3 ≤ n, m ≤ 1000, 1 ≤ k ≤ min(n*m, 100 000)$) байх ба музейн хэмжээсүүд ба эхлэх байрлалуудын тоо байна.

Дараагийн $n$ мөр бүрт $m$ тэмдэгт '$.$', '$*$' байх ба музейн тодорхойломж байна. Хүрээний бүх нүднүүд битүү ба Игор музейгээс гарч чадахгүй.

Сүүлийн $k$ мөр бүрт хоёр бүхэл тоон утга $x$ ба $y$ ($1 ≤ x ≤ n, 1 ≤ y ≤ m$) байх ба харгалзан Игорийн эхлэх байрлалийн мөр ба багана байна. Мөрүүд дээрээс доош чиглэлтэй дугаарлагдах ба баганууд зүүнээс баруун тийш дугаарлагдана. Бүх эхлэх байрлалууд нь хоосон нүд байна.

Гаралт

Игор харгалзах эхлэлийн цэгээс эхлэсэн бол харж чадах зургийн хамгийн их тоог илэрхийлэх $k$ ширхэг бүхэл тоон утгыг хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

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