Задание выполняется с использованием прилагаемых файлов

Квадрат разлинован на клеток . Крабу нужно перейти через пляж со стороны джунглей (верхняя строка) в сторону океана (нижняя строка). Он может начать переход с любой клетки верхней строки и закончить на любой клетке нижней строки. Краб за одно перемещение может попасть в одну из трех клеток следующей строки: на клетку вниз или на одну из клеток слева/справа от нижней. При попытке сходить влево или вправо (без смены строки), назад (в предыдущую строку) или за границы поля Краба съедают. На пляже могут быть песчаные ловушки (помечены красным). При попадании в ловушку Краб становится чьим-то ужином. В каждой клетке квадрата лежит монета достоинством от до . Посетив клетку, Краб забирает монету с собой; это также относится к начальной и конечной клетке маршрута Краба.

Определите максимальную денежную сумму, которую может собрать Краб, пройдя со стороны джунглей (сверху) до океана (снизу).