Администрация города Загреба решила построить новую парковку. Для этого будет использован участок земли прямоугольной формы, который можно представить как матрицу из $N$ строк и $M$ столбцов. Чтобы привлечь гостей и тем самым увеличить доход, мэр решил разместить на заранее определенных участках земли фонтаны, колодцы и другие подобные сооружения. Оставшиеся участки предназначены для движения транспорта и будут переоборудованы в один из двух типов:
- парковочные места или
- поля для свободного движения транспорта.
Транспортные средства могут перемещаться по парковке, перемещаясь на каждом шаге на соседнее поле в одном из четырех направлений (север, юг, восток или запад). Парковка должна быть спроектирована таким образом, чтобы в любой момент времени с каждого парковочного места можно было добраться до входа/выхода, который находится в верхнем левом углу (на пересечении первой строки и первого столбца). Это означает, что транспортные средства, стоящие на парковочных местах, не должны блокировать выезд другим транспортным средствам. Другими словами, каждое припаркованное транспортное средство должно иметь возможность выехать с парковки, не перемещая другие припаркованные транспортные средства.
Помогите мэру определить максимально возможное количество парковочных мест для заданного участка земли.
Примечание: Поле в первой строке и первом столбце является входом на парковку, оно не предназначено для парковки и всегда будет свободным.
Входные данные
В первой строке заданы натуральные числа $N$ и $M$ ($1 \le N \le 6$, $1 \le M \le 100$), количество строк и столбцов участка земли. Следующие $N$ строк содержат по $M$ символов, описывающих вид участка: символом ‘x’ обозначено поле, на котором будет построен фонтан, остальные поля обозначены символом ‘.’ и будут переоборудованы под парковку.
Выходные данные
В единственной строке выведите искомое максимально возможное количество парковочных мест.
Оценивание
| Подзадача | Количество баллов | Дополнительные ограничения |
|---|---|---|
| 1 | 10 | $N, M \le 4$ |
| 2 | 10 | $N = 2$ |
| 3 | 20 | $N = 3$ |
| 4 | 20 | $N = 4$ |
| 5 | 20 | $N = 5$ |
| 6 | 20 | $N = 6$ |
PROBNI PRIMJERI
Входные данные 1
3 3 ... .x. ...
Выходные данные 1
2
Входные данные 2
3 3 ... ..x ...
Выходные данные 2
4
Входные данные 3
3 6 .x..x. ..x.x. ......
Выходные данные 3
3
Входные данные 4
4 5 ....x ....x ..x.. .x..x
Выходные данные 4
7
Примечание
Пояснение к четвертому примеру: один из возможных вариантов расположения парковочных мест:
.PPPx ....x .Px.P PxP.x