Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: potvynis.in

Rezultatų failas: potvynis.out

Jei norite pateikti savo sprendimą - prisijunkite.

Potvynis

Kalnuotoje vietovėje, apsuptoje keturių jūrų, prasidėjo stiprūs lietūs. Šie lietūs yra tokie stiprūs, kad kiekvieną valandą virš kalnų, turinčių mažiausią aukštį (o taip pat ir į jūras), subėga vieno metro vandens sluoksnis.

Jums reikės rasti po kelių valandų, apsėmus kai kuriuos vietovės kalnus, atsiras upelis, jungiantis šiaurinę ir pietinę jūras (ar kai šios jūros susijungs į vieną).

Į vietovę galima žiūrėti kaip į HxW dydžio matricą M. Šios matricos elementai 1\\leqM[i][j]\\leq10^9 parodo kokio aukščio kalnas stovi atitinkamoje vietoje. Pradinio laiko momentu jūrų aukštis sutampa su žemiausio kalno aukščiu.

Įvestis

Pirmoje pradinių duomenų eilutėje bus pateikti du skaičiai H ir W (1\\leqH,W\\leq1000). Tolimesniuose H eilučių bus pateikta po W skaičių, nurodančių vietovės kalnų aukščius.

Pavyzdys

Pradiniai duomenys Rezultatai 
3 4
1 1 9 9
1 1 5 1
9 9 9 1
 
5

Pastaba

Tikrinti ar jūros yra sujungtos reikia po vandens pakilimo, t.y. jei visos viršūnės yra vienodame aukštyje, atsakymas bus 1.