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

\begin{document}

\renewcommand{\tl}{$5$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача AT22. МУХЪЛ}
\renewcommand{\header}{
	ЛАГЕР ШКОЛА ЗА\\
	ПОДГОТОВКА НА РАЗШИРЕНИТЕ ОТБОРИ\\
	София, 27 юни 2026 г.\\
	Група A -- 11, 12 клас
}

\indent Сашка има дълга дървена дъска, разделена на $N$ еднакви участъка, номерирани от $1$ до $N$. В началото всички участъци са заразени с мухъл.

За да спаси дъската, Сашка разполага с препарат против мухъл и $M$ възможни почиствания с препарата. За почистване $i$ са дадени денят $T_i$, в която вечер може да бъде извършено, участъците от $L_i$ до $R_i$, които засяга, и цената $C_i$. Ако Сашка избере това почистване, то премахва мухъла от всеки все още заразен участък в отсечката от $L_i$ до $R_i$.

Мухълът обаче не стои на едно място. Ако даден участък е заразен сутринта на някой ден, то до обяд на същия ден заразата се разпространява и към двата му съседни участъка, ако такива съществуват. Затова веднъж почистен участък може по-късно да се зарази отново. В рамките на един ден Сашка може да извърши произволен брой почиствания.

Формално, всеки ден първо мухълът се разпространява от всички заразени участъци към техните съседи, а след това Сашка извършва всички избрани от нея почиствания за този ден.

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

Напишете програма \textbf{\texttt{mold}}, която намира тази минимална сума или установява, че това е невъзможно.

\subsection{Детайли по реализацията}
Трябва да предадете файла \texttt{mold.cpp}, който включва \texttt{mold.h} и реализира функцията

\begin{lstlisting}
long long min_cost(int N, std::vector<int> T, std::vector<int> L,
                   std::vector<int> R, std::vector<int> C)
\end{lstlisting}
където:
\begin{itemize}
	\item $N$ е броят участъци на дъската;
	\item векторите $T$, $L$, $R$ и $C$ имат по $M$ елемента и описват почистванията;
	\item за почистване $i$ стойностите $T[i]$, $L[i]$, $R[i]$ и $C[i]$ съответно означават деня на почистването, левия край на отсечката, десния край на отсечката и цената му.
\end{itemize}

Функцията се извиква точно веднъж.

Тя трябва да върне минималната обща цена, необходима след извършване на избраните почиствания да не остане нито един заразен участък, или $-1$, ако това е невъзможно.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $1 \leq N \leq 10^9$;
	\item $1 \leq M \leq 100\ 000$;
	\item $1 \leq T_i \leq 10^9$;
	\item $1 \leq L_i \leq R_i \leq N$;
	\item $1 \leq C_i \leq 10^9$.
\end{itemize}

\pagebreak
\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{Необходими подзадачи} & $M$ & \textbf{Допълнителни ограничения}\\
		\hline
		$0$ & $0$ & $-$ & $-$ & Примерите. \\
		\hline
		$1$ & $4$ & $-$ & $\leq 100\ 000$ & $T_i = 1$ за всяко $i$ \\
		\hline
		$2$ & $5$ & $0$ & $\leq 16$ & $-$ \\
		\hline
		$3$ & $30$ & $0, 2$ & $\leq 5\ 000$ & $-$ \\
		\hline
		$4$ & $61$ & $0 - 3$ & $\leq 100\ 000$ & $-$ \\
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}
\FloatBarrier

\subsection{Локален грейдър}

Формат на входа:
\begin{itemize}
	\item ред $1$: две цели числа $N\ M$;
	\item редове $2$ до $M + 1$: по четири цели числа $T_i\ L_i\ R_i\ C_i$ -- описание на едно почистване.
\end{itemize}

Формат на изхода:
\begin{itemize}
	\item ред $1$: стойността, върната от функцията \texttt{min\_cost}.
\end{itemize}

Форматът на примерите следва формата на локалния грейдър.

\subsection{Примери}

\begin{table}[ht]
	\begin{tblr}{|l|l|}
		\hline
		\textbf{Вход} & \textbf{Изход} \\
		\hline
		\texttt{\makecell[lt]{10 5\\2 5 10 3\\1 1 6 5\\5 2 8 3\\7 6 10 4\\4 1 3 1}} & \texttt{7} \\
		\hline
		\texttt{\makecell[lt]{10 5\\2 6 10 3\\1 1 5 5\\5 2 7 3\\8 6 10 4\\4 1 3 1}} & \texttt{-1} \\
		\hline
		\texttt{\makecell[lt]{10 5\\1 5 10 4\\1 1 6 5\\1 4 8 3\\1 6 10 3\\1 1 3 1}} & \texttt{7} \\
		\hline
	\end{tblr}
\end{table}

\pagebreak
\subsection{Обяснение на примера}

В първия пример Сашка избира почиствания $1$, $3$ и $5$ за обща цена $3 + 3 + 1 = 7$.

Вечерта на ден $2$ почистване $1$ премахва мухъла от участъци $5,\dots,10$. През следващите два дни мухълът постепенно се разпространява обратно до участъци $5$ и $6$. Вечерта на ден $4$ почистване $5$ премахва мухъла от участъци $1,2,3$. На обяд на ден $5$ мухълът отново достига до участъци $3$ и $7$. Накрая вечерта на ден $5$ почистване $3$ премахва мухъла от участъци $3,\dots,7$ и дъската остава напълно чиста.

\end{document}