Квадрат разлинован на N×N клеток (1 <, N <, 30). Роботу нужно перейти поле с левой верхней клетки до правой нижней. Робот может двигаться по клеткам вправо, вниз или вправо и вниз (по диагонали). В каждой клетке поля лежит монета достоинством от 1 до 100. Робот не может ходить через стены или выходить за границы поля. Робот собирает все монеты по пройденному маршруту, включая верхнюю левую и нижнюю правую клетки.
Определите минимально возможную денежную сумму, которую может собрать робот и общее количество клеток этого маршрута. В ответе укажите два числа: сначала минимальную сумму, затем общее количество клеток маршрута с минимальную суммой. Если маршрутов с равной суммой несколько, выбрать наиболее короткий.