Nosaukums
Taisnstūrveida tepiķis (tepikis)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
92%

Definīcija

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!

 


Ievaddatu raksturojums

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.

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.

 


Izvaddatu raksturojums

Vienīgajā rindā jāizvada vesels skaitlis - lielākā tepiķa laukums.

 


Piezīmes

 
Uzdevums izmantots informātikas olimpiādē NOI2002.


Paraugdati

Stdin
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
Stdout
14

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.