You are given a grid representing a treasure map of size m x n, where each cell contains an integer indicating the number of coins in that location. A cell with 0 means it is empty and contains no coins.

Your goal is to collect the maximum number of coins while following these rules:

Whenever you step on a cell, you collect all the coins from that location.
You can move one step in any of the four directions: left, right, up, or down.
You cannot visit an empty cell, meaning a cell with 0 coins.
You cannot revisit the same cell within the current path after collecting its coins.
You can start and stop collecting coins from any cell that has coins.

Return the maximum number of coins you can collect.

Example 1:

Input: grid = [[0,5,0],[4,7,6],[0,9,0]]
Output: 22
Explanation:
[[0,5,0],
 [4,7,6],
 [0,9,0]]
Path to get the maximum coins is: 9 -> 7 -> 6.

Example 2:

Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,2,0],[14,0,25]]
Output: 28
Explanation:
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,2,0],
 [14,0,25]]
Path to get the maximum coins is: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

Constraints

m == grid.length

n == grid[i].length

1 <= m, n <= 15

0 <= grid[i][j] <= 100

There are at most 25 cells containing coins.

75. Path with Maximum Coins