Baseins

ID: baseins
Grūtība: 4/5
Laika limits: 1

Uzdevums

Senos laikos baseinu būve notika sekojoši: Tika izbrīvēts taisnstūra veida zemes laukums ar izmēriem m un n metri. Šo laukumu sadalīja 1*1 metru lielās rūtiņās, tādējādi iegūstot m*n rūtiņas. Pēc tam katrā rūtiņā tika nolikts vai nu viens ideāli noslīpēts granīta kubs ar šķautnes garumu 1 metrs, vai arī šādu ideālu kubu tornis.
Kubi bija noslīpēti tik precīzi, ka pietika diviem kubiem saskarties kaut vai tikai ar šķautni, lai ūdens šajā vietā cauri netecētu.
Lietum līstot, šādā "kubu sistēmā" varēja uzkrāties zināms daudzums ūdens.
Uzrakstiet programmu, kas nosaka, kāds lielākais ūdens daudzums kubikmetros var uzkrāties šādā baseinā!

Ievaddati

Teksta faila baseins.in pirmajā rindā doti divi naturāli skaitļi m un n, kas nosaka taisnstūra laukuma malu garumus metros (0 < m, n <= 100).
Nākošajās m faila rindās dots pa n naturāliem skaitļiem.
Faila i+1-ās rindas j-tais skaitlis norāda laukuma i-tās rindas j-tajā rūtiņā novietotā kubu torņa augstumu (kubu skaitu). Zināms, ka katrā rūtiņā novietots vismaz viens kubs un nevienā rūtiņā novietotā kubu torņa augstums nepārsniedz 10000.

Izvaddati

Teksta faila baseins.out vienīgajā rindā jāizvada viena vesela skaitļa vērtība - lielākais ūdens daudzums kubikmetros, kāds var uzkrāties dotajā baseinā.

Piemērs

baseins.in baseins.out
3 6
3 3 4 5 4 2
3 1 3 2 1 3
6 3 1 4 3 1
5

Zīmējumā parādīts tukša un maksimāli piepildīta dotā baseina skats no augšas.


© 2001-2002 olimps! http://www.lio.lv/olimps/