Самая полная модель

C++17, C++20, Python 3, Go, Kotlindaily-space-005-maximum-reconstruction

В ящик размером $K\times K\times K$ можно помещать единичные кубики. Допустимые координаты кубиков — целые $0\le x,y,z<K$ ; в каждой ячейке может находиться не более одного кубика. Даны три силуэта размера $K\times K$ .

В виде спереди кубик $(x,y,z)$ отмечает строку $y$ , столбец $x$ .
В виде сверху он отмечает строку $z$ , столбец $x$ .
В виде справа он отмечает строку $y$ , столбец $K-1-z$ .

Нумерация начинается с нуля. В силуэте стоит 1, если на этом луче находится хотя бы один кубик, и 0 иначе. Ящик и силуэты закреплены: сдвигать или вращать их нельзя.

Найдите наибольшее число кубиков в модели, дающей в точности эти силуэты. Модель не обязана быть связной и может быть пустой. Если ни одной подходящей модели нет, выведите -1.

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

Первая строка содержит целое $K$ ( $1\le K\le30$ ). Затем идут $3K$ строк длины $K$ , состоящих из 0 и 1: $K$ строк вида спереди, $K$ строк вида сверху и $K$ строк вида справа. Строки каждого вида перечислены сверху вниз, без дополнительных разделителей.

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

Выведите максимальное число кубиков или -1, если силуэты несовместимы.

Примеры

Пример 1

Input

Output

Согласованные проекции пространственной цепочки.

Пример 2

Input

Output

-1

Требования разных видов противоречат друг другу.

Пример 3

Input

Output

Полностью пустые проекции допускают пустую модель.

Пример 4

Input

Output

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

Примечания

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