| Codeforces Beta Round 74 (Div. 1 Only) |
|---|
| Закончено |
Рассмотрим следующую игру. Имеется прямоугольное поле размера 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). Ее ход можно проследить на следующей картинке:
Все остальные фишки приносят меньше очков.
