F2 - Fukušima

V okolí elektrárne Fukušima je opäť radiácia. Vy sa nachádzame vo vnútri a chcete sa dostať do bezpečia.

Úloha

K dispozícii máte obrazovku, ktorá ukazuje plán okolia ako štvorcovú sieť. Na každom políčku ukazuje hodnotu radiácie. Vy stojíte na políčku v ľavom hornom rohu štvorcovej siete a chcete sa dostať na políčko v pravom dolnom rohu. Aby Vás ožiarilo čo najmenej, musíte minimalizovať maximálnu hodnotu radiácie po ceste. Ak existuje viacero ciest, ktoré spĺňajú túto podmienku, vyberte sa po najkratšej z nich. Po štvorcovej siete sa môžete pohybovať všetkými ôsmimi smermi. Dĺžka cesty je počet navštívených políčok včítane začiatočného a koncového.

Vstup

Prvý riadok vstupu obsahuje dve celé čísla A a B oddelené medzerou. Číslo A určuje počet riadkov a B počet stĺpcov v štvorcovej sieti. Ďalej na A riadkoch nasleduje plán okolia. Na každom z nich je B celých čísel C_i,j oddelených medzerou, ktoré udávajú hodnotu radiácie na danom políčku v štvorcovej sieti.

F1

1 ≤ A, B ≤ 10
0 ≤ C_i,j ≤ 10

F2

1 ≤ A, B ≤ 1000
0 ≤ C_i,j ≤ 10000

Výstup

Výstup má obsahovať dve čísla oddelené medzerou. Prvé má udávať maximálnu hodnotu radiácie na ceste a druhé dĺžku cesty.

Príklad

Vstup:

4 4
1 1 1 2
2 2 1 2
2 1 2 2
1 1 1 1

Výstup:

1 6