Задача #2897

(М. Попков) Квадрат разлинован на N x N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из трех команд: влево, вниз или диагональ. По команде влево Робот перемещается в соседнюю левую клетку, по команде вниз – в соседнюю нижнюю, по команде диагональ – влево и вниз одновременно.

При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой, если достоинство монеты в этой ячейке не делится на 3, иначе он оставляет ячейку нетронутой; всё это также относится к начальной и конечной клетке маршрута Робота.

Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из правой верхней клетки в левую нижнюю. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.