egipt
In Egiptul antic piscinele erau construite astfel:
- se alegea o zona dreptunghiulara de lungime
m metri si latime n metri;
se trasa in aceasta zona un caroiaj format din patrate de 1 metru x 1 metru, obtinandu-se astfel mxn patrate, organizate in m linii si n coloane;
se pregateau cuburi din piatra cu latura 1 metru, atat de perfecte incat alaturarea a doua cuburi era ermetica;
in fiecare patrat din zona dreptunghiulara aleasa era plasat un turn format din unul sau mai multe cuburi suprapuse;
se turna apa in piscina.
Cerinta
Scrieti un program care sa determine volumul maxim de apa care incape intr-o piscina din Egiptul antic (exprimat in metri cubi).Date de intrare
Fisierul de intrare egipt.in contine:
- pe prima linie cele doua numere naturale
m si n separate printr-un spatiu;
pe fiecare dintre urmatoarele m linii se afla cate n numere naturale separate prin cate un spatiu; al j-lea numar din linia i+1 este Hi,j, adica inaltimea turnului de cuburi plasat in patratul din linia i, coloana j a caroiajului.
Date de iesire
Fisierul de iesire egipt.out
contine o singura linie pe care se afla volumul maxim de apa care incape in piscina (exprimat in metri cubi).
Restrictii
-
1 <= n, m <= 100
- 1 <= Hi,j <= 10000, pentru orice 1 <= i <= m, 1 <= j <= n
Exemplu
|
egipt.in
|
egipt.out
|
Explicatie |
|
3 6
3 3 4 5 4 2
3 1 3 2 1 3
6 3 1 4 3 1
|
5
|
In figura urmatoare este ilustrata piscina goala si piscina plina cu apa:
|
Timp maxim de executie/test: 0.1 secunde.