%LuaLaTex
\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{2cm}

\begin{document}

\renewcommand{\tl}{$0.2$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача GT3. ЛЮТЕНИЦА}
\addauthor{}{2025}{01}{01}
\renewcommand{\header}{
	ТРЕНИРОВЪЧНО СЪСТЕЗАНИЕ\\
    МОМИЧЕТА\\
	Пловдив, 12-14 юни 2026 г.\\
	Група G
}

Сашка решава да си напазарува лютеница за зимата. Има \(n\) различни вида лютеница, номерирани от \(1\) до \(n\).

Видовете лютеница се продават в два магазина -- Магазин А и Магазин В. Един вид лютеница може да бъде закупен само от един от двата магазина.

Магазин А предлага \(i\)-тия вид лютеница на цена \(a_{i}\) лева за буркан, а Магазин В го предлага на цена \(b_{i}\) лева.

Сашка разполага с бюджет до \(x\) лева за покупки в Магазин А и до \(y\) лева за покупки в Магазин В.

Тя иска да закупи максимален брой различни видове лютеница, като за всеки вид избере един от двата магазина, от който да го купи.

\vspace{-2pt}
\subsection{Вход}
От първия ред на стандартния вход се въвеждат три цели числа \(n\), \(x\) и \(y\) -- броят на видовете лютеница и бюджетите в двата магазина.

Следват $n$ реда, всеки с по две числа - $a_i$ и $b_i$, съответно цените в магазин A и магазин B на $i$-ата лютеница.

\vspace{-2pt}
\subsection{Изход}

На стандартния изход изведете едно цяло число -- максималния брой различни видове лютеница, които Сашка може да закупи.

\vspace{-2pt}
\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
    \item \(1 \le n \le 2000\)
    \item \(0 \le x, y \le 10\,000\)
    \item \(0 \le a_{i}, b_{i} \le 10\,000\) (за всички \(1 \leq i \leq n\))
\end{itemize}

\vspace{-2pt}

%\begin{itemize}
%    \item (11 точки) \(x, y \le 500\), \(n \le 12\)
%    \item (24 точки) \(x, y \le 500\), \(n \le 200\)
%    \item (9 точки) \(y = 0\)
%    \item (10 точки) \(b[i] = b[j]\) (за всички \(0 \le i, j \le n-1\))
%    \item (14 точки) \(a[i] = b[i]\) (за всички \(0 \le i \le n-1\))
%    \item (32 точки) Няма допълнителни ограничения
%\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
\centering
\begin{tblr}{|Q[c,m]|Q[c,m]|X[c,m]|X[c,m]|}
\hline
\textbf{№} &
\textbf{Точки} &
\textbf{Необходими подзадачи} &
\textbf{Други ограничения} \\
\hline

$0$ & $-$ & $-$ & Примерните тестове \\
\hline

$1$ & $11$ & $0$ &
$x,y \le 500,\; n \le 12$ \\
\hline

$2$ & $24$ & $0-1$ &
$x,y \le 500,\; n \le 200$ \\
\hline

$3$ & $9$ & $-$ &
$y = 0$ \\
\hline

$4$ & $10$ & $-$ &
$b_i = b_j$ за всички $1 \le i,j \le n$ \\
\hline

$5$ & $14$ & $-$ &
$a_i = b_i$ за всички $1 \le i \le n$ \\
\hline

$6$ & $32$ & $0-5$ &
Няма допълнителни ограничения \\
\hline

\end{tblr}
\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}
\newpage

\subsection{Пример}
\begin{table}[H]
	\begin{tblr}{|l|l|X[j]|}
		\hline
		\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера} \\
		\hline
		\texttt{\makecell[lt]{3 2 3\\
		2 2 \\
		1 3 \\
		4 2 \\
		}}
		& 
		\texttt{\makecell[lt]{
		2 \\
		}}
		& 
		{
		  Сашка може да купи втория вид лютеница от Магазин А за 1 лев и третия вид от Магазин В за 2 лева. \\ Така общо купува 2 различни вида.
		}
		\\
		\hline
	    \texttt{\makecell[lt]{5 6 12 \\
        5 3 \\
        1 5 \\
        5 4 \\
        6 6 \\
        3 7 \\
		}}
		& 
		\texttt{\makecell[lt]{
		4 \\
		}}
        &
        {
            
        } \\
        \hline
		
	\end{tblr}
\end{table}
	
\end{document}