Matice

Matici K(N,c,d) definujeme jako celočíselnou čtvercovou matici velikosti NxN, která má na hlavní i vedlejší diagonále pouze nuly. V oblasti nad hlavní a nad vedlejší diagonálou a v oblasti pod hlavni a pod vedlejší diagonálou obsahuje matice K(N,c,d) pouze hodnoty c. Všude jinde obsahuje hodnoty d.
Příklad: K(7, 4, 1): 
  0  4  4  4  4  4  0
  1  0  4  4  4  0  1
  1  1  0  4  0  1  1
  1  1  1  0  1  1  1 
  1  1  0  4  0  1  1
  1  0  4  4  4  0  1
  0  4  4  4  4  4  0
Pro daná celá čísla N, a1 ≤ a2, b1 ≤ b2 defnujeme množinu matic M(N, a1, a2, b1, b2) takto:
M(N, a1, a2, b1, b2) = {K(N, c, d) | a1 ≤ c ≤ a2, b1 ≤ d ≤ b2 }.

Dvě matice A a B z množiny M(N, a1, a2, b1, b2) prohlásíme za spřízněné, pokud součet jejich norem nepřevýší danou celočíselnou hodnotu D. Normu libovolné matice Z definujeme jako horní celou část odmocniny ze součtu druhých mocnin všech prvků Z.

Připomínáme, že libovolný neorientovaný graf je souvislý právě tehdy, když mezi dvěma jeho libovolnými uzly u a v vede cesta. Graf je také souvislý právě tehdy, když při prohledávání do šířky nebo do hloubky, které zahájíme v libovolném uzlu grafu, navštívíme postupně všechny uzly grafu.

Každou matici množiny M(N, a1, a2, b1, b2) prohlásíme za uzel neorientovaného grafu G. Hrana mezi dvěma různými uzly u a v grafu G existuje právě tehdy, pokud matice odpovídající uzlům u a v jsou navzájem spřízněné.

Máme určit minimální možnou hodnotu D, pro níž graf G zkonstruovaný nad množinou M bude souvislý.

Vstup

Na vstupu jsou dva řádky. První řádek obsahuje čísla N, a1, a2, b1, b2 v tomto pořadí oddělená mezerou. Hodnota N leží v rozmezí 3..100, ostatní hodnoty leží v rozmezí −100..100. Platí a1 ≤ a2, b1 ≤ b2.
Druhý řádek obsahuje dvě celá čísla D1 a D2 oddělená mezerou, 0 ≤ D1 ≤ D2 ≤ 106.

Výstup

Na výstupu je jediný řádek obsahující celé číslo D, pro které platí D1 ≤ D ≤ D2 a přitom D je minimální možná celočíselná hodnota, pro níž graf G zkonstruovaný nad množinou M je souvislý. Pokud žádné celé číslo D splňující uvedené podmínky neexistuje, vystoupí číslo −1.

Příklad 1

Vstup: 
3 0 1 1 2
1 7
Výstup: 
6

Příklad 2

Vstup: 
3 -1 0 1 2
2 5
Výstup: 
-1

Příklad 3

Vstup: 
100 10 20 10 20
1000 5000
Výstup: 
2970

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data