Пират в подземелье, Нужен второй алгоритм Опции

[1nFinite]

Прошу помомите написать алгоритм задачи
Пират в подземелье

В поисках драгоценных камней пират проваливается в подземелье. План подземелья - матрица NxM комнат с драгоценными камнями. Камни из одной комнаты имеют одинаковую стоимость. Пирату в каждой комнате разрешается взять с собой лишь один камень и следовать в любую другую соседнюю с ним комнату. Каждую из комнат пират может посещать неоднократно .

Требуется составить алгоритм- программу определения маршрута посещения пиратом К комнат лабиринта таким образом , чтобы он набрал камней на максимально возможную сумму .

Входные и Выходные . В первой строке входного файла содержаться числа N,M и K
В следующих N строках распологается матрица NxM лабиринта. Каждый элемент матрицы представляется стоимостью камня соответствующей комнаты. Маршрут начинается с левой верхней угловой комнаты лабиринта.

Выходной файл должен содержать единственное число, равное общей стоимости взятых с собой камней.

Пример файла исходных данных:

3 4 7
1 1 1 1
1 1 2 1
1 1 2 3

Выходной файл для данного примера:
12.

[1nFinite]

N=3 M=4 K=7
NxM - размер матрицы
K - количество комнат
В данном примере который я написал там
число ходов 7 комнат и он(пират) должет набрать на эти 7 ходов 12 камней
Начанается ход с верхнего левого угла
Он должен набрать на максимальную возможную сумму