Хоссам купил новый участок земли длины \(n\) и ширины \(m\), он поделил его на \(n \cdot m\) квадратов, каждый из которых имеет размер \(1\times1\).
Так как имя Хоссам начинается с латинской буквы 'H', он хочет нарисовать большую букву 'H' путем построения стен размера \(1\times1\) на некоторых квадратах земли. Каждый квадрат земли \(1\times1\) может быть одного из трех типов: идеальный, средний, или плохой.
Процесс возведения стен для формирования буквы 'H' имеет следующие ограничения:
- Буква должна состоять из одной горизонтальной и двух вертикальных линий.
- Вертикальные линии не должны находиться в одном и том же или соседних столбцах.
- Вертикальные линии должны начинаться в одной строке и заканчиваться в одной строке (и, следовательно, иметь одинаковую длину).
- Горизонтальная линия должна соединять вертикальные линии, но не должна пересекать их.
- Горизонтальная линия может находиться в любом ряду между вертикальными линиями (не только в середине), кроме верхней и нижней. (С горизонтальной линией в верхнем ряду буква выглядит как 'n', а в нижнем ряду как 'U'.)
- Запрещается возводить стены в квадратах плохого качества.
- Вы можете использовать не более одного квадрата среднего качества.
- Вы можете использовать любое количество квадратов идеального качества.
Найдите максимальное количество стен, которые можно использовать для рисования буквы 'H'.
Смотрите примечание для получения дополнительных разъяснений.
Выходные данные
Выведите одно целое число — максимальное число стен в букве 'H'.
Если никак не возможно написать букву 'H', выведите \(0\).
Примечание
В первом тестовом примере никак не возможно написать букву 'H'.
Во втором примере, картинка показывает участок и некоторые допустимые буквы 'H'. Идеальные, средние, и плохие квадраты выделены белым, желтым, и черным цветом соответственно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
#m.
.#.
|
0
|
|
2
|
7 8
...#.m..
..m...m.
.#..#.m#
...m..m.
m.......
..#.m.mm
......m.
|
16
|