Рабочее место участника

В доме-лабиринте все комнаты имеют квадратную форму, в каждой стене комнаты по одной двери, ведущей либо в соседнюю комнату, либо наружу. Но все двери в доме имеют ручку только с одной стороны, и с той стороны, где нет ручки, дверь открыть нельзя. Двери на плане обозначены символами '>' (больше), '<' (меньше), 'v' (строчная латинская буква вэ), '^' (крышечка). Направление уголка соответствует направлению, в котором можно проходить дверь. В доме спрятано от 1 до 5 золотых монет, обозначенных на плане символом '$' (доллар). Текущая позиция обозначена символом '*' (звездочка). Символ '.' (точка) обозначает пустую комнату. Символ '+' (плюс) обозначает пересечение стен.

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

Во входном файле содержится план дома-лабиринта. Количество строк нечётно и не превышает 101, все строки имеют одинаковую нечётную длину от 3 до 101. В нечётно-нечётных позициях плана находятся только символы '+'. В чётно-чётных только символы '.', '*', '$'. Символы для дверей могут находиться только в нечётно-чётных позициях плана.

В первой строке выходного файла вывести максимальное количество собранных монет, а затем через пробел количество открытых дверей. Если выйти из лабиринта невозможно, то вывести одно число `-1`.

+v+^+^+
<*>.>$<
+v+v+^+
<$<$>.>
+^+v+v+

2 4