Shortcut Maze Challenge

The first line contains three space-separated integers: 'N', 'M', and 'K'.

The next 'N' lines each contain 'M' space-separated integers, representing the cost grid.

The next line contains an integer 'S', the number of available shortcuts.

The next 'S' lines each contain four space-separated integers: r1 c1 r2 c2, representing a shortcut from (r1, c1) to (r2, c2). Indices are 0-based.

Print a single integer representing the minimum cost to reach the destination.

If the destination is unreachable, print -1.

The cost of the starting cell (0, 0) is included in the total path cost.

You can use at most 'K' shortcuts in total.

Sample Input 1:

3 3 1
1 100 100
1 100 100
1 1 1
1
0 0 2 2

Sample Output 1:

2

Explanation for Sample 1:

The standard path through the grid would be forced through high-cost cells.
The optimal path is to use the shortcut immediately at the start `(0,0)`.
The cost is the starting cell's cost `cost(0,0)` plus the destination cell's cost `cost(2,2)`.
Total Cost = 1 + 1 = 2. This is much cheaper than any path involving the cells with cost 100.

Sample Input 2:

2 2 1
1 1
10 1
1
1 0 0 1

Sample Output 2:

3

Explanation for Sample 2:

Path without shortcut: `(0,0) -> (0,1) -> (1,1)`. Cost = `1 + 1 + 1 = 3`.
Path with shortcut: `(0,0) -> (1,0)`. Cost to reach shortcut = `1 + 10 = 11`. At `(1,0)`, jump to `(0,1)`. Cost to land = `cost(0,1) = 1`. Total cost to be at `(0,1)` is `11 + 1 = 12`.    From `(0,1)` move to `(1,1)`. Final cost = `12 + 1 = 13`.
The path without the shortcut is cheaper.

Sample Input 3:

2 2 1
1 100
100 1
0

Sample Output 3:

-1

Expected Time Complexity:

The expected time complexity is O(K * N * M * log(K * N * M)).

Constraints:

1 <= N, M <= 100
0 <= K <= 10
1 <= grid[r][c] <= 1000
0 <= S <= 50

Time limit: 1 sec