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

[1nFinite]

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

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

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

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

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

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

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

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