Shortcut Maze Challenge

You are navigating a grid of size 'N' x 'M'. Each cell (r, c) has a positive integer cost, grid[r][c], to step on it. Your journey starts at the top-left corner (0, 0) and must end at the bottom-right corner (N-1, M-1).

You can move from your current cell in two directions: down to the cell below it or right to the cell next to it. The cost of a move is the value of the destination cell.

Additionally, some cells contain hidden shortcuts. A shortcut allows you to jump instantly from its location to a different cell in the grid. The jump itself is free, but you still incur the cost of the destination cell you land on. You are given an integer 'K', which is the maximum number of shortcuts you are allowed to use throughout your entire journey.

Your task is to find the minimum total cost to travel from (0, 0) to (N-1, M-1).

Input Format:

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.

Output Format:

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

If the destination is unreachable, print -1.

Note:

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

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