Reward Path Finder

Problem Description

You are given a 2D grid represented as an N x M matrix. Each cell in the grid has one of the following values:

• A non-negative integer representing the reward points available at that cell.
• A value of -1, indicating that the cell is an obstacle and cannot be traversed.

The journey starts at the top-left cell (0, 0) and must end at the bottom-right cell (N-1, M-1). Movement is allowed in four directions: up, down, left, or right (no diagonal moves). You cannot enter a cell that contains an obstacle (-1).

Your task is to write a function that determines whether there exists a path from the starting cell to the destination such that the total sum of reward points collected along the path is at least a given target value K. If such a path exists, your function should also return the length of the shortest path (measured in the number of moves) that meets or exceeds the reward threshold K. If no valid path exists, return an appropriate indication (for example, -1).

Input

• A 2D list (or array) representing the grid, where each element is an integer (either a reward value ≥ 0 or -1 for an obstacle).
• An integer K representing the minimum total reward points required, where K ≥ 0.

Output

• The length of the shortest valid path that collects at least K reward points, or an indication (such as -1) if there is no valid path.

Constraints

• Grid dimensions (N and M) are such that the grid can be as large as 1000 x 1000.
• Reward values in the grid and K are non-negative integers.
• You may assume that the top-left and bottom-right cells are not obstacles.

Example

Consider the following grid and reward threshold:

grid = [
  [1, 2, -1, 4],
  [2, 3, 2, 1],
  [0, -1, 0, 3],
  [4, 1, 2, 0]
]
K = 10

A valid solution is to find the shortest path from the top-left to the bottom-right cell that collects at least 10 rewards in total along the way.

Instructions

Design and implement your solution for this problem. Make sure your code is efficient and well-structured, as it may need to handle large grids. Your implementation should be self-contained and should not rely on any external hints or guides.