В четвёртом подвиге Рустама, легендарного героя из Шахнаме, старая ведьма создала волшебный лабиринт, чтобы заманить его в ловушку. Лабиринт представляет собой прямоугольную сетку, состоящую из \(n\) строк и \(m\) столбцов. Каждая клетка в лабиринте указывает в определенном направлении: вверх, вниз, влево или вправо. Ведьма заколдовала Рустама так, что всякий раз, когда он находится в клетке, он перемещается в следующую клетку в направлении, указанном этой клеткой.
Если Рустам в конце концов выйдет из лабиринта, он освободится от чар ведьмы и победит ее. Однако, если он будет вечно блуждать по лабиринту, то он останется там навсегда.
Ведьма еще не определила направления для всех клеток. Она хочет назначить направления для неуказанных клеток таким образом, чтобы количество клеток, начав из которых Рустам будет пойман навсегда, было максимальным. Ваша задача — найти это количество.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество клеток, начиная из которых Рустам будет заперт навсегда, после оптимального назначения направлений неопределенным ячейкам.
Примечание
Назовём плохими клетки, начиная в которых Рустам не сможет выбраться. Остальные клетки назовём хорошими.
В первом наборе входных данных все клетки будут хорошими, независимо от ваших действий.
Во втором наборе входных данных, если вы назначите ? значения, как показано на рисунке ниже, все клетки будут плохими:
В третьем наборе входных данных, если вы назначите ? значения, как показано на рисунке ниже, у вас будет \(5\) плохих клеток (клетки, закрашенные красным):
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 3
UUU
L?R
DDD
2 3
???
???
3 3
?U?
R?L
RDL
|
0
6
5
|