C. Игра с фишками
ограничение по времени на тест
4 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим следующую игру. Имеется прямоугольное поле размера n × m, в некоторых клетках которого находятся фишки.

На каждой фишке нарисована стрелка. Таким образом, каждая фишка на поле показывает в одном из направлений: вверх, вниз, налево или направо.

Игрок может выбрать одну из фишек и сделать ей ход.

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

В результате хода игрок получает некоторое количество очков, равное количеству удаленных фишек.

По заданной начальной расстановке фишек определите максимальное количество очков, которое может получить игрок за один ход, а также количество таких ходов.

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

В первой строке даны два целых числа n и m (1 ≤ n, m, n × m ≤ 5000). Далее идут n строк по m символов в каждой — описание игрового поля. «.» означает, что данная клетка пуста. «L», «R», «U», «D» означают, что в данной клетке есть фишка и стрелка на ней указывает налево, направо, вверх или вниз соответственно.

Гарантируется, что на поле имеется хотя бы одна фишка.

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

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

Примеры
Входные данные
4 4
DRLD
U.UL
.UUR
RDDL
Выходные данные
10 1
Входные данные
3 5
.D...
RRRLL
.U...
Выходные данные
6 2
Примечание

В первом примере наибольшее количество очков приносит фишка в позиции (3, 3). Ее ход можно проследить на следующей картинке:

Все остальные фишки приносят меньше очков.