Bergskedja

문제

Torunn bor i ett bergigt bostadsområde som består av ett $n\times mn\; \backslash times\; m$-rutnät med en tomt i varje ruta. Torunn bor på rutan längst upp till vänster i rutnätet. Tyvärr har en extra jobbig hyresgäst nyligen flyttat in, så Torunn har bestämt sig för att sälja sin bostad och flytta någon annanstans. Först måste han dock ta reda på hur mycket bostaden är värd.

Varje ruta i rutnätet har en höjd. Alla höjder är olika, så låt oss för enkelhets skull anta att höjderna är $1,2,3,\cdots ,n\cdot m1,\; 2,\; 3,\; \backslash cdots,\; n\backslash cdot\; m$. Tomter med högre höjd är värda mer på bostadsmarknaden, så Torunn vill ta reda på höjden på sin tomt. Han har därför gått runt till varje ruta i rutnätet och kollat hur många angränsande rutor som är lägre. En ruta anses vara angränsande om den delar en sida (rutor som inte ligger längs bostadsområdets kant har alltså $44$ angränsande rutor).

Skriv ett program som, givet informationen Torunn samlade in, hittar minsta och största möjliga höjd för hennes tomt.

입력

Första raden innehåller två heltal $nn$ och $mm$ ($1\le n,m\le 81\; \backslash leq\; n,m\; \backslash leq\; 8$), antalet rader och kolumner i rutnätet.

De följande $nn$ raderna innehåller en sträng av längd $mm$ var. Detta rutnät utgör informationen som Torunn samlade in, varje siffra motsvarar alltså antalet angränsande rutor som har lägre höjd än rutan som siffran står i. Det är garanterat att det finns minst ett sätt att tilldela höjderna $1,2,\cdots ,n\cdot m1,\; 2,\; \backslash cdots,\; n\backslash cdot\; m$ till rutorna så att den insamlade informationen är korrekt. Notera att värdena som samlats in alltid kommer vara mellan $00$ och $44$.

출력

Skriv ut två heltal, den minsta och den största möjliga höjden på rutan i övre vänstra hörnet.

힌트

[이미지 1]

Två möjliga fördelningar av höjder som stämmer överens med exempel $11$.