% Idee: Semjon/Sona Kravtšenko
% Tekst: Semjon/Sona Kravtšenko
% Tõlge: Semjon/Sona Kravtšenko, Ahto Truu

\documentclass[a4paper,11pt]{article}
\usepackage[et]{../../eio}

\begin{document}
\begin{ol}{\eio}{\ev 4.12.2025}{\yle}{}
\begin{yl}{4}{Kõrgeim torn}{torn}{1 sek / 3 sek}{60 punkti}

Sirel mängib värviliste risttahukakujuliste klotsidega ja tahab ehitada neist torni.
Selleks, et torn püsiks kindlalt, peab selle alumine klots täielikult toetuma ristkülikukujulise laua pinnale
ja iga järgmine klots tornis peab täielikult toetuma eelnevale klotsile.

Et viia ellu oma kunstiline visioon, tahab Sirel, et kõik klotsid oleksid joondatud ristsuunaliselt ---
klotse võib pöörata, kuid iga kasutatud klotsi külgtahud peavad olema paralleelsed laua servadega.
Tornis ei pea kasutama kõiki klotse, aga Sirel tahab kasutada klotse ainult etteantud järjekorras.

Aita Sirelil leida kõiki tingimusi rahuldava torni maksimaalne võimalik kõrgus.

\sis Sisendi esimesel real on kolm tühikutega eraldatud täisarvu: klotside arv $N$ ($1 \le N \le 10^3$) ning
laua laius $W$ ja pikkus $L$ ($1 \le W \le L \le 10^6$).

Järgmisel $N$ real on igaühel kolm tühikutega eraldatud täisarvu $A_i$, $B_i$, $C_i$: klotsi $i$ mõõdud ($1 \le A_i, B_i, C_i \le 10^6$).

\val Väljastada üks täisarv $H$: kõrgeima kindlalt püsiva ristsuunaliselt joondatud torni kõrgus, milles
klotse on kasutatud ainult antud järjekorras.

\nde[0]{3cm}{3cm}

Selles näites peab maksimaalse kõrguse saavutamiseks kasutama ära kõik kolm klotsi.
Klotse võib kasutada ilma pööramata.
Pane tähele, et keskmise klotsi pööramine nii, et selle kõrgus oleks üle $1$,
ei võimaldaks ehitada kõrgemat torni, sest siis ei saaks viimast klotsi kasutada.

\nde[1]{3cm}{3cm}

Selles näites ei saa esimest klotsi kasutada, sest see ei mahu ristsuunaliselt joondatuna lauale.
Teise klotsi kõige väiksemale tahule pööramisega saaks ehitada torni, millle kõrgus on $14$.
Aga see pole parim võimalik lahendus.
Et ehitada torn kõrgusega $15$, paneb Sirel teise klotsi lauale suurimale tahule,
jätab kolmanda klotsi vahele ning saab siis ära kasutada neljanda ja viienda klotsi.

\clearpage

\hnd \testidgrupis
\begin{xenum0}
    \item (0 punkti) \naitedlyhem
    \item (15 punkti) $N \le 12$; $A_i = B_i = C_i$ iga $1 \le i \le N$ korral.
    \item (10 punkti) $N \le 12$.
    \item (20 punkti) $A_i = B_i = C_i$ iga $1 \le i \le N$ korral.
    \item (15 punkti) \piiranguteta
\end{xenum0}
\alamylkaupa

\end{yl}
\end{ol}
\end{document}
