Taisnstūrveida tepiķis

Uzdevums

Pilī katras zāles grīda ir sadalīta kvadrātos. Uz dažiem kvadrātiem atrodas kolonnas (plānā šie kvadrāti apzīmēti ar '#'), bet pārējie ir brīvi (plānā apzīmēti ar '.'). Vienas zāles plāns var būt šāds:

...#...#..
..##.#....
......#.#.
.#........
.........#
.....#.#..

Zālē nepieciešams izvietot taisnstūrveida tepiķi, kura malas būtu paralēlas zāles malām un kura laukums būtu lielākais iespējamais. Skaidrs, ka tepiķis var aizņemt tikai brīvos kvadrātus. Iepriekšminētajai zālei lielākais iespējamais tepiķis ir 14 kvadrātus liels un plānā atzīmēts ar '*':

...#...#..
..##.#....
......#.#.
.#*******.
..*******#
.....#.#..

Uzrakstiet programmu, kas dotam zāles plānam nosaka lielākā tajā izvietojamā tepiķa laukumu!

Ievaddati

Teksta faila tepikis.dat pirmajā rindā doti divi naturāli skaitļi R(1≤R≤20) un K(1 ≤K≤40), kas atdalīti ar tukšumsimbolu. R ir rindu, bet K kolonnu skaits zāles plānā Rindas tiek numurētas pēc kārtas ar skaitļiem no 1 līdz R, sākot no augšas, bet kolonnas ar skaitļiem no 1 līdz K, sākot no kreisās puses uz labo.

Faila otrajā rindā dots vesels skaitlis N, kas apzīmē kolonnu skaitu zālē. Katrā no nākošajām N faila rindām katrā dots pa diviem naturāliem skaitļiem, kas atdalīti ar tukšumsimbolu. Katras rindas pirmais skaitlis apzīmē rindu, bet otrais kolonnu, kurā atrodas kolonna.

Izvaddati

Teksta faila tepikis.rez vienīgajā rindā jāizvada vesels skaitlis - lielākā tepiķa laukums.

Piemērs

tepikis.dat	tepikis.rez
6 10 11 1 4 1 8 2 6 5 10 4 2 2 4 2 3 6 6 3 7 3 9 6 8	14

Atsauces