Gudrinieku ciema zinātnieki pēta peļu intelektu. Tie ir izveidojuši dažādus labirintus un tajos novietojuši kārumus. Pēc tam tie labirintā palaiž peli un apskata, cik kārumu peles spēj atrast. Taču ir novērota problēma – daudzas no gudrākajām pelēm ir saēdušās tik daudz kārumu, ka tās ir kļuvušas resnas. Palīdzi zinātniekiem noskaidrot, cik kārumu dotajai pelei labirintā ir iespējams atrast.

Labirits sastāv no N × M kvadrātainām šūnām ur šūna ir vai nu neapstaigājams šķērslis (apzīmējam ar 'X'), apstaigājama šūna bez kāruma (apzīmēta ar '.'), vai apstaigājama šūna ar kārumu (apzīmēta ar '*'). 

Peles labirintā tiek apskatītas kā kvadrāts platumā un augstumā K. Šūnas, kurās pele sākotnēji atrodas, ir apstaigājamas un apzīmētas ar 'P'. Pele pārvietojas pa vienai šūnai vai nu vertikāli, vai horizontāli. Un tā var apēst visu, kam tā uzkāpj virsū.

Izvadiet vienu skaitli – cik kārumu pelei ir sasniedzami dotajā labirintā.

Ilustrācija

Pirmajā rindā doti divi veseli skaitļi N un M (3 < N, M ≤ 2000), labirinta izmērs.

Otrajā rindā dots vesels skaitlis K (0 < K < N, M), peles izmērs.

Tālāk seko N rindas ar M kolonām – labirinta apraksts.

izvadiet viens veselu skaitli, cik kārumus var apēst pele.

Apakšgrupas:

• 20% testu K = 1
• 20% testu N, M ≤ 500