% Idee: Bartosz Tarnawski
% Tekst: Bartosz Tarnawski, Ahto Truu

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

\usepackage{tikz}

\begin{document}
\begin{ol}{\eio}{\vv 15.03.2026}{\yle}{}
\begin{yl}{2}{Linnaplaan}{linn}{1 sek / 3 sek}{100 punkti}

Byteasar on lõpuks leidnud ideaalse asukoha oma kuningriigi uue pealinna ehitamiseks. Ta pole veel kindel, kui suur linn saab olema, kuid ta on defineerinud ristkoordinaatide süsteemi ja otsustanud, et linn saab olema ristkülik, mille küljed on paralleelsed koordinaattelgedega ning mille üks tipp on punktis $(0, 0)$ ja vastastipp punktis $(W, H)$, kus $W, H > 0$ on seni veel määramata täisarvud.

Byteasar plaanib rajada $N+1$ paralleelset puiesteed ja nummerdada need $0$ kuni $N$, kusjuures puiestee $i$ ühendab punkte $(X_i, 0)$ ja $(X_i, H)$. Samuti plaanib ta rajada $M+1$ paralleelset tänavat nummerdada need $0$ kuni $M$, kusjuures tänav $j$ ühendab punkte $(0, Y_j)$ ja $(W, Y_j)$. Tehnilistel põhjustel peavad kõik (seni veel määramata) koordinaadid $X_i$ ja $Y_j$ olema täisarvud, mis vastavad tingimustele $0 = X_0 < X_1 < \ldots < X_N = W$ ja $0 = Y_0 < Y_1 < \ldots < Y_M = H$. Puiesteed ja tänavad jagavad linna $N \times M$ ristkülikukujuliseks krundiks, kus puiesteede $i-1$ ja $i$ ning tänavate $j-1$ ja $j$ vahelise krundi tähis on $(i, j)$.

Byteasar on suhelnud $L$ tulevase elanikuga ja on kogunud teavet nende eelistuste kohta. Ta teab, et $k$-s tulevane elanik ($k = 1, 2, \ldots, L$) soovib elada krundil $(A_k, B_k)$ ja tahab, et selle pindala oleks täpselt $P_k$ ruutmeetrit ($1 \le P_k \le R$, kus $R$ on sisendis antud parameeter). Krundid, millest ükski tulevane elanik pole huvitatud, võivad olla mis tahes pindalaga.

Byteasar palus kontrollida, kas on võimalik rahuldada kõigi tulevaste elanike nõuded, ja kui on, siis leida linna vähim võimalik pindala.

\sis
Sisendi esimesel real on neli täisarvu $N$, $M$, $L$ ja $R$ ($1 \le N, M \le 10^3$, $1 \le L \le N \cdot M$, $1 \le R \le 10^6$). Järgmised $L$ rida kirjeldavad tulevaste elanike nõudeid; nende hulgas $i$-ndal real on kolm täisarvu $A_i$, $B_i$ ja $P_i$ ($1 \le A_i \le N$, $1 \le B_i \le M$, $1 \le P_i \le R$). Võib eeldada, et $A_i \ne A_j$ või $B_i \ne B_j$, kui $i \ne j$.

\val
Esimesele reale väljastada sõna `\verb'YES'', kui kõigi tulevaste elanike nõuded on võimalik rahuldada, või sõna `\verb'NO'' vastasel juhul. Kui kõigi nõuete rahuldamine on võimalik, väljastada teisele reale täisarv $S$, kõigi tulevaste elanike nõudeid rahuldava linna minimaalne pindala.

\hnd \testidgrupis
\begin{xenum0}
  \item (0 punkti) \naitedlyhem
  \item (9 punkti) $N = 1$.
  \item (11 punkti) $N, M \le 6$, $R \le 100$.
  \item (16 punkti) $N, M \le 100$, $R \le 1\,000$.
  \item (19 punkti) $R \le 1\,000$.
  \item (21 punkti) $L = N \cdot M$.
  \item (24 punkti) \piiranguteta
\end{xenum0}

Programm, mis väljastab kõigis grupi testides õige esimese rea, aga mõnes testis, kus linna ehitamine on võimalik, vale teise rea, saab 50\% selle grupi punktidest.

Selles ülesandes on lahendustel lubatud tavapärase 256 MB asemel kasutada 1 GB mälu.

\clearpage

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

$X_0 = 0$, $X_1 = 7$, $X_2 = 8$ ja $Y_0 = 0$, $Y_1 = 1$, $Y_2 = 3$. See paigutus on näidatud alloleval joonisel. Igal krundil olev arv näitab selle pindala. Paksus kirjas arvud näitavad tulevaste elanike nõutud pindalasid. Mittepaksus kirjas arvud näitavad pindalasid, mille kohta nõudeid pole.

\begin{center}
\begin{tikzpicture}
  \draw[thick] (0, 0) -- (7, 0) -- (7, -2) -- (0, -2) -- cycle;
  \draw[thick] (0, -2) -- (7, -2) -- (7, -3) -- (0, -3) -- cycle;
  \draw[thick] (7, -2) -- (8, -2) -- (8, -3) -- (7, -3) -- cycle;
  \draw[thick] (7, 0) -- (8, 0) -- (8, -2) -- (7, -2) -- cycle;

  \draw[fill=black] (0, -3) circle (0.05);
  \draw[fill=black] (8, 0) circle (0.05);
  \draw[fill=black] (0, -2) circle (0.05);
  \draw[fill=black] (0, 0) circle (0.05);
  \draw[fill=black] (7, 0) circle (0.05);
  \draw[fill=black] (7, -3) circle (0.05);
  \draw[fill=black] (8, -3) circle (0.05);
  \draw[fill=black] (8, -2) circle (0.05);

  \node at (0, -3) [below left] {(0,0)};
  \node at (8, 0) [above right] {(8,3)};
  \node at (0, -2) [left] {(0,1)};
  \node at (0, 0) [above left] {(0,3)};
  \node at (7, 0) [above] {(7,3)};
  \node at (7, -3) [below] {(7,0)};
  \node at (8, -3) [below right] {(8,0)};
  \node at (8, -2) [right] {(8,1)};

  \draw[black] (3.5, -1) node {{\bf 14}};
  \draw[black] (3.5, -2.5) node {{\bf 7}};
  \draw[black] (7.5, -1) node {2};
  \draw[black] (7.5, -2.5) node {{\bf 1}};
\end{tikzpicture}
\end{center}

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

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