Fishmonger Toll Optimization Problem

A fishmonger needs to transport goods from a port to a market, crossing multiple states each requiring a toll. The goal is to minimize the toll costs while ensuring the journey is completed within a specified time limit to prevent spoilage of the goods.

Explanation:

You are provided with ‘N’ states and a time limit ‘M’. Your task is to determine the smallest toll amount the fishmonger needs to pay to reach the market from the port within the given time. The journey starts at the 0th state (port) and ends at the 'N'-1 state (market).

Input:

First line: Integer ‘T’ for the number of test cases.
For each test case:
- Two integers ‘N’ and ‘M’ indicating the number of states and the maximum allowable time.
- Next ‘N’ lines: ‘N’ integers representing the ‘Time’ matrix indicating time from state ‘i’ to state ‘j’.
- Next ‘N’ lines: ‘N’ integers representing the ‘Toll’ matrix indicating toll cost from state ‘i’ to state ‘j’.

Output:

For each test case, output the minimum toll cost required to reach the market from the port within the given time, or -1 if it is not possible.

Example:

Input:
 N = 2, M = 4,
 Time = [[0, 2], [3, 0]],
 Toll = [[0, 10], [5, 0]]
Output:
 10

Constraints:

• 1 <= T <= 10
• 2 <= N <= 50
• 1 <= M <= 1000
• 0 <= Toll[i][j] <= 10⁸
• 0 <= Time[i][j] <= 1000

Note:

You do not need to print anything; your implementation should return the result for each test case.