C. Клубы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
4 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Обратите внимание на необычное ограничение по памяти в этой задаче.

Сотрудники MDCS (Microsoft Development Center Serbia, сербского центра разработок Майкрософта) любят вечеринки. Обычно они ходят в ночные клубы в пятницу и субботу.

Всего в MDCS работает N людей, а в городе всего есть N клубов. К сожалению, если в ночном клубе будет больше одного сотрудника Майкрософта, то уровень крутизны этой вечеринки возрастает до небес, и вечеринка заканчивается, так что владельцы клуба никогда не позволяют более, чем одному сотруднику Майкрософта войти в их клуб в течение недели (так, на всякий случай).

Вы организуете ночную жизнь сотрудников Майкрософта и у Вас есть статистика о том, насколько каждому сотруднику нравятся вечеринки в пятницу и субботу, для всех клубов.

Вам надо распределить людей по клубам, максимизируя общую сумму их довольства (они настолько довольны, насколько им нравится выбранный клуб), при этом половина людей должна пойти клубиться в пятницу, а другая половина — в субботу.

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

В первой строке записано целое число N — количество сотрудников в MDCS.

Затем следует матрица размера N × N, где элемент на пересечении i-й строки и j-го столбца — целое число, обозначающее, насколько i-му человеку нравится клубиться в j-м клубе в пятницу.

Затем следует ещё одна матрица размера N × N, где элемент на пересечении i-й строки и j-го столбце — целое число, обозначающее, насколько i-му человеку нравится клубиться в j-м клубе в субботу.

  • 2 ≤ N ≤ 20
  • N четное
  • 0 ≤  уровень довольства  ≤ 106
  • Все значения являются целочисленными
Выходные данные

Вывод должен содержать единственное целое число — максимальную возможную сумму счастья.

Примеры
Входные данные
4
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
5 8 7 1
6 9 81 3
55 78 1 6
1 1 1 1
Выходные данные
167
Примечание

Распределение людей по клубам в примере:

Пятница: 1-й человек идет в 4-й клуб (4 единицы довольства), а 4-й человек идет в 1-й клуб (4 единицы довольства).

Суббота: 2-й человек идет в 3-й клуб (81 единица довольства), а 3-й человек идет во 2-й клуб (78 единиц довольства).

4 + 4 + 81 + 78 = 167.