B. Долг Фрирен и магический архив
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Прошли годы после победы над Королём демонов. Люди меняются быстро — у них короткая жизнь и ещё короче терпение к хаосу в архивах. Фрирен это, конечно, не волнует... пока не начинает волновать.

Во втором путешествии она всё чаще сталкивается с последствиями собственных обещаний. Десятки гильдий до сих пор хранят её старые записи о заклинаниях, артефактах и магических исследованиях. Чтобы закрыть один из долгов, Фрирен должна объединить два независимых каталога заклинаний в единый официальный свиток.

В архивах лежат две хроники:

  • Хроника $$$A$$$ — записи самой Фрирен, представленные массивом $$$a$$$ длины $$$n$$$;
  • Хроника $$$B$$$ — записи гильдии магов, представленные массивом $$$b$$$ длины $$$m$$$.

Каждая запись — это неотрицательное целое число, обозначающее магический индекс заклинания. Необходимо составить массив $$$c$$$ длины $$$n+m$$$, являющийся «переплетением» массивов $$$a$$$ и $$$b$$$, то есть содержащий каждый элемент массива $$$a$$$ и каждый элемент массива $$$b$$$, строго в том же порядке, в котором они следовали в $$$a$$$ и в $$$b$$$.

Более формально, требуется выбрать $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_n \le n + m$$$, после чего, определив $$$c_{i_j} = a_j$$$, а остальные индексы массива $$$c$$$ заполнить последовательно элементами массива $$$b$$$.

Определим оптимальность массива $$$c$$$ следующим образом.

  1. Рассмотрим префиксы массива $$$c$$$: сначала только первый элемент, затем первые два элемента, затем первые три и так далее, вплоть до всего массива.
  2. Для каждого такого префикса вычисляется его mex — минимальное целое неотрицательное число, отсутствующее среди элементов этого префикса.
  3. Оптимальность массива $$$c$$$ — это сумма значений mex для всех его префиксов.

Требуется выбрать способ «переплетения» массивов $$$a$$$ и $$$b$$$, при котором оптимальность итогового массива $$$c$$$ будет наибольшей.

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$t$$$ — длины массивов $$$a$$$ и $$$b$$$, и параметр $$$t$$$, влияющий на формат вывода ($$$1 \le n, m \le 8 \cdot 10^3$$$; $$$t \in \{1, 2\}$$$).

Вторая строка содержит $$$n$$$ неотрицательных целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^6$$$).

Третья строка содержит $$$m$$$ неотрицательных целых чисел $$$b_1, b_2, \dots, b_m$$$ ($$$0 \le b_i \le 10^6$$$).

Выходные данные

Если $$$t = 1$$$, выведите единственное число — наибольшую возможную оптимальность массива $$$c$$$.

Если $$$t = 2$$$, выведите в первой строке максимальную оптимальность, а во второй строке — любой подходящий под условие массив $$$c$$$, достигающий этой стоимости.

Система оценки

Баллы за группы начисляются только в случае, если все тесты соответствующей группы и необходимых групп успешно пройдены.

ГруппаБаллы Дополнительные ограничения Необходимые группы Информация о проверке
0–примеры из условияполная
15$$$n+m \le 20$$$; $$$t=1$$$первая ошибка
Примеры
Входные данные
2 2 1
0 1
0 2
Выходные данные
8
Входные данные
4 4 2
1 0 3 1
2 0 4 3
Выходные данные
28
1 0 2 3 0 4 3 1
Входные данные
7 6 1
1 0 2 2 5 0 3
4 1 0 6 2 3
Выходные данные
57