\begin{center}
\textit{Автор задачи: Александр Бабин, разработчик: Иван Пискарев}
\end{center}

\section*{$O(S! \cdot S)$}
Переберём все возможные способы переезда и выберем лучший.

\section*{$O(S^3 \cdot \log m)$}
Будем искать ответ бинарным поиском.
Хотим проверить, что можно организовать переезд так, чтобы максимальное расстояние было не больше $k$.
Построим двудольный граф, где вершины в левой доли соответствуют местам до переезда, а в правой местам после переезда.
Ребро между двумя вершинами присутствует, если расстояние между их домами не превосходит $k$.
Несложно видеть, что переезд с расстоянием не больше $k$ осуществить возможно тогда и только тогда, когда в графе существует полное паросочетание.

Найти максимальное паросочетание в двудольном графе можно алгоритмом Куна за $O(nm)$, где $n$ -- число вершин, $m$ -- число рёбер.

\section*{$O(2^A \cdot AB)$}

Вместо явного поиска максимального паросочетания достаточно лишь проверить условие леммы Холла.
А именно, проверить, что с каждым подмножеством $X$ вершин левой доли напрямую связано хотя бы $|X|$ вершин правой.
Так как такое множество вершин правой доли зависит только от множества клеток, в которых находятся вершины множества $X$, то достаточно рассмотреть всего $2^A$ вариантов такого множества.

\section*{$O(m)$ при $n = 1$}

Упорядочим места до переезда и места после переезда по возрастанию $j$-координаты.
Заметим, что способ переезда,
где жилец из $k$-го места до переезда переезжает в $k$-ое место после переезда, оптимален.
Найти максимальное расстояние при таком способе переезда можно проходом с двумя указателями.

% \pagebreak % delete later

\section*{$O(m \cdot \log m)$ при $n \le 2$}




Сделаем бинпоиск по ответу.
Хотим проверить, можно ли организовать переезд так, чтобы максимальное расстояние было не больше $k$.
Для этого проверим условие леммы Холла.

$ $

Пусть $X$ -- подмножество домов.
\begin{itemize}
    \item
          Обозначим за $W_1(X)$ и $W_2(X)$ -- суммарное количество жителей в $X$ до и после переезда соответственно.
    \item
          Обозначим за $N(X)$ -- множество домов на расстоянии не более $k$ от $X$.
\end{itemize}

Тогда условие леммы Холла равносильно выполнению неравенства $W_2(N(X)) - W_1(X) \ge 0$ для всех $X$.
Чтобы это проверить, найдём минимальное значение $f(X) = W_2(N(X)) - W_1(X)$ и сравним его с нулём.

Для нахождения минимального значения воспользуемся динамическим программированием:
пусть \texttt{dp[i][mask]} -- минимальное значение $f(X)$, если
\begin{itemize}
    \item $X$ состоит только из домов до $i$-го столбца включительно
    \item $X$ содержит хотя бы один дом в $i$-ом столбце
    \item \texttt{mask} -- пересечение $X$ с $i$-ым столбцом
          % \item В $W_2$ учитываются только дома до $i$-го столбца включительно
\end{itemize}

Заметим, что если $X$ содержит хотя бы один дом в $i$-ом столбце, то вхождение дома строго правее $i$-го столбца в $N(X)$ не зависит от вхождения в $X$ домов строго левее $i$-го столбца и наоборот.
Значит для пересчёта достаточно перебрать ближайший справа дом, который добавится в $X$.

Заметим, что достаточно пересчитываться только в столбцы на $1$ и $2k$ домов правее.
Так как при пересчёте на не больше чем $2k - 1$ столбцов включение всех пропущенных столбцов в $X$ не сделает хуже, а значит такой пересчёт будет не хуже нескольких пересчётов на один столбец вправо.
И при пересчёте больше чем на $2k$ столбцов при значении \texttt{dp} не меньше $0$ его не выгодно использовать, а при значении меньше нуля уже был найден контрпример к условию леммы Холла.


\section*{$O(m)$ при $n \le 2$}

От бинпоиска можно избавиться.
Заметим, что от склейки первой и второй строк ответ либо не изменится, либо уменьшится на один (так как расстояние между любыми двумя местами либо не изменилось, либо уменьшилось на один).
Значит достаточно решить такую же задачу для на один меньшего $n$ и после сделать проверку для одного значения $k$.



% \section*{$O(m  \cdot n^2 \cdot 3^{2n})$}
\section*{Полное решение $O(mn^2 \cdot 3^{2n})$}

Пусть у нас есть $\mathbb{N}$ красок различных цветов, пронумерованных числами $0, 1, 2, ...$.


Введём несколько обозначений:

\begin{itemize}
    \item Для множества домов $X$ определим раскраску домов $C(X)$, в которой дом покрашен в цвет с номером, равным расстоянию до ближайшего дома из $X$.
    \item Для раскраски домов $C$ определим множества домов $X(C), Y(C)$, состоящие из домов цвета $0$ и домов цветов $0, 1, 2, ..., k$ соответственно.
    \item Определим стоимость раскраски $C$ как $f(C) = W_2(Y(C)) - W_1(X(C))$.
    \item Назовём раскраску хорошей, если разница номеров цветов любых двух соседних домов не превосходит $1$.
\end{itemize}

Заметим, что

\begin{itemize}
    \item $f(X) = f(C(X))$
    \item $C(X)$ -- хорошая раскраска
    \item Если $C$ -- хорошая раскраска, то $f(C) \ge f(X(C))$
\end{itemize}

В предыдущем решении мы сводили задачу к вычислению $\displaystyle \min_X f(X)$.

Заметим, что из трёх свойств выше следует, что $\displaystyle \min_X f(X) = \min_{C \text{ хорошая}} f(C)$.

Значит достаточно научиться вычислять $\displaystyle \min_{C \text{ хорошая}} f(C)$.



Для этого пересчитаем \texttt{dp[i][mask]} -- минимальное значение $f(C)$ по всем хорошим раскраскам $C$, если
\begin{itemize}
    \item В $W_1, W_2$ учитываются только жители домов до $i$-го столбца включительно
    \item \texttt{mask} кодирует номера цветов домов $i$-го столба
\end{itemize}

\subsection*{Пересчёт за $O(m^2n \cdot 3^{2n})$}

Попробуем сначала просто пересчитывать \texttt{dp[i+1]} через \texttt{dp[i]}.

Заметим, что не имеет смысла рассматривать раскраски, в которых нет цвета $0$, значит максимальный цвет не превосходит $n + m = O(m)$.
Заметим, что если цвет первого дома в столбце фиксирован, то оставшиеся можно раскрасить не более $3^{n-1}$ способами, чтобы при этом раскраска получилась хорошей.

Значит возможных значений \texttt{mask} не более $O(m \cdot 3^n)$.

Заметим, что из \texttt{dp[i][mask]} можно сделать пересчёт не более чем в $3^n$ состояний в \texttt{dp[i+1]}.

Один пересчёт из \texttt{dp[i][mask1]} в \texttt{dp[i+1][mask2]}, очевидно, можно сделать за $O(n)$.

Итого у нас есть $O(m^2 \cdot 3^n)$ состояний \texttt{dp}, из каждого из которых мы делаем не более $3^n$ пересчётов, каждый из которых работает за $O(n)$.
Значит время работы такого решения это $O(m^2 \cdot n \cdot 3^{2n})$


Заметим, что достаточно рассматривать только раскраски из цветов $0, 1, ..., \text{k}, \text{k} + 1$.
Это позволяет решить задачу за $O(\text{ans} \cdot mn \cdot 3^{2n})$.

\subsection*{Пересчёт за $O(mn^2 \cdot 3^{2n})$}

Будем явно хранить только те состояния, где в \texttt{mask} присутствует цвет $0$.
Заметим, что таких значений \texttt{mask} ровно $3^{n-1}$ (выбираем $n-1$ разностей соседних из $\left\{-1, 0, +1\right\}$ и прибавляем константу так, чтобы минимум был равен нулю).

Заметим, что достаточно пересчитываться только на $1,2, ..., 2n$ или $2k - 2 (n - 1), ..., 2k - 1, 2k$ столбцов направо.
Пусть мы пересчитались из столбца $i_1$ в столбец $i_2$.
Если $i_2 - i_1 < 2k - 2(n-1)$, то, добавив столбцы с $i_1 + n$ по $i_2 - n$ в множество $X$, мы не увеличим стоимость, так как $Y(C)$ останется прежним.
Если же $i_2 - i_1 > 2k$, то при значении \texttt{dp} меньше нуля (с учётом жителей в столбцах правее $i_1$) уже можно заканчивать, а при значении хотя бы ноль его не выгодно использовать при пересчёте.

Итого у нас $m \cdot 3^{n-1}$ состояний, из каждого состояния мы делаем не более $4n \cdot 3^{n-1}$ пересчётов, каждый из которых делается за $O(n)$.

