#include <vector>
#include <queue>
#include <utility>
#include <tuple>
#include <algorithm>
using namespace std;

using queue_entry = tuple<int, long long, int, int>;
struct comp_func_queue
{
public:
    bool operator()(queue_entry &lhs, queue_entry &rhs) const
    {
        // 아무리 적게 이동해도 ((m-1) - y) + ((n-1) - x)만큼을 더 가야 하므로 지금까지의 이동거리에 더해준다
        // m-1과 n-1은 모든 식에 동일하게 등장하므로 제거해서 비교하여도 상관이 없다.
        const int dist_l = get<0>(lhs) - get<2>(lhs) - get<3>(lhs);
        const int dist_r = get<0>(rhs) - get<2>(rhs) - get<3>(rhs);

        if (dist_l == dist_r)
        {
            return get<1>(lhs) > get<1>(rhs);
        }
        return dist_l > dist_r;
    }
};


int cut[50][50];
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, int s, vector<vector<int>> time_map) {
    int move_distance = 0;
    int sum_of_talk_time = 0;

    int dy[4] = { 0,1,0,-1 };
    int dx[4] = { 1,0,-1,0 };

    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            cut[i][j] = 0x7fffffff;
        }
    }

    priority_queue<queue_entry, vector<queue_entry>, comp_func_queue> pq;
    pq.emplace(0, 0, 0, 0);
    vector<int> answer(2);
    while (true)
    {
        auto top = pq.top();
        pq.pop();

        int y = get<2>(top);
        int x = get<3>(top);

        if (cut[y][x] <= get<1>(top)) continue;
        cut[y][x] = get<1>(top);

        if (y == m - 1 && x == n - 1)
        {
            answer[0] = get<0>(top);
            answer[1] = get<1>(top);
            break;
        }

        for (int dir = 0; dir<4; dir++)
        {
            const int ny = y + dy[dir];
            const int nx = x + dx[dir];
            if (!(ny >= 0 && ny < m && nx >= 0 && nx < n)) continue;
            if (time_map[ny][nx] == -1) continue;

            queue_entry entry(get<0>(top) + 1, get<1>(top) + time_map[ny][nx], ny, nx);
            if (get<1>(entry) > s) continue; // 이동함으로써 t의 합이 s를 초과하게 되는 경우
            if (get<1>(entry) >= cut[ny][nx]) continue; // 더 적은 이동으로 더 적은 대화시간에 도달하는게 가능한 경우 고려X

            pq.emplace(entry);
        }
    }

    return answer;
}