class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int dx[] = { 0, 0, -1, 1 };
        int dy[] = { -1, 1, 0, 0 };
        
        int n = grid.size();
        int m = grid[0].size();
        int inf = 1e9;
        vector<vector<int>> dist ( n, vector<int>(m, inf) );
        
        dist[0][0] = 0;
        
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
        
        pq.push( { grid[0][0], 0, 0, 0 } );
        
        while ( !pq.empty() ) {
            vector<int> currNode = pq.top();
            pq.pop();
            
            int curK = currNode[0];
            int d = currNode[1];
            int x = currNode[2];
            int y = currNode[3];
            
            if ( d > dist[x][y] ) continue;
            
            for ( int i = 0; i < 4; i++ ) {
                int x1 = x + dx[i];
                int y1 = y + dy[i];
                
                if ( x1 >= 0 && x1 < n && y1 >= 0 && y1 < m ) {
                    if ( 1 + d < dist[x1][y1] && grid[x1][y1] + curK <= k  ) {
                        dist[x1][y1] = d + 1;
                        pq.push( {grid[x1][y1] + curK, dist[x1][y1], x1, y1} );
                    }
                }
            }
        }
        
        if ( dist[n-1][m-1] == inf ) dist[n-1][m-1] = -1;
        return dist[n-1][m-1];
    }
};