AlgoLiga 2018

Jako, że algorytmika powoli zaczyna mnie nudzić postanowiłem zająć się sztuką współczesną. Moją artystyczną duszę poruszyła ostatnio fenomenalna instalacja złożona z betonowych klocków o kształcie sześcianu i objętości 1 dm³, znajdująca się na terenie jednej z budów. Stosy klocków ułożone były, na pace gigantycznej ciężarówki, w m rzędów po n stosów w każdym. Wysokości stosów mogły się różnić. Od razu zrozumiałem, że to dzieło to rozpaczliwy krzyk autora, który próbuje zwrócić naszą uwagę na ucisk betonowych sześcianów o objętości 1 dm³ w dzisiejszym świecie.

Postanowiłem z tego dzieła zrobić arcydzieło. Obok ciężarówki stała betoniarka zawierająca l litrów mieszanki. Zdecydowałem, że obuduję instalację odpowiednio wysokimi drewnianymi ścianami, a następnie zaleję posiadaną mieszanką. Chcę uzyskać kształt prostopadłościanu, którego wysokość w dm jest możliwie największym elementem ciągu Fibonacciego. Jeżeli po zalaniu dzieło nie będzie miało kształtu prostopadłościanu albo jego wysokość w dm nie będzie elementem ciągu Fibonacciego to usunę niepotrzebną górną część, tak aby spełniało założenia. Pytanie brzmi jaką wysokość w dm będzie miało moje arcydzieło?

Wejście

W pierwszej linii wejścia znajdują się trzy liczby naturalne m ∈ [1;1000], n ∈ [1;1000] i l ∈ [1;10¹²] opisane powyżej. W kolejnych m liniach znajduje się po n liczb całkowitych, są to wysokości poszczególnych stosów klocków podane w dm. Wysokość każdego stosu zawiera się w przedziale [1;10⁶].

Wyjście

Na wyjściu należy wypisać szukaną wysokość arcydzieła.

Przykład

Wejście

2 2 11
1 8
2 4

Wyjście

5

Wyjaśnienie

Po zalaniu stosy będą miały następujące wysokości:

6 8
6 6

W związku z czym muszę przyciąć dzieło do wysokości 5.