# Maximal Minimum Value Path II

Given a two 2D integer array, find the max score of a path from the upper left cell to bottom right cell that doesn't visit any of the cells twice. The score of a path is the minimum value in that path.

### Examples

#### Example 1:

##### Input:
``````[7,5,3]
[2,0,9]
[4,5,9]``````
##### Explanation:

Here are some paths from `[0,0]` to `[2,2]` and the minimum value on each path:

path: `7->2->4->5->9`, minimum value on this path: `2`

path: `7->2->0->9->9`, minimum value on this path: `0`

path: `7->2->0->5->9`, minimum value on this path: `0`

Notice: the path can move all four directions. (not only right and down. ALL FOUR DIRECTIONS)

Here `7->2->0->5->3->9->9` is also a path, and the minimum value on this path is `0`.

The path doesn't visit the same cell twice. So `7->2->0->5->3->9->0->5->9` is not a path.

In the end the max score(the min value) of all the paths is `3`.

## Implementation

 `1` `1` ``from typing import List`` `2` `2` `3` `3` ``def maxPathScore(matrix: List[List[int]]) -> int:`` `4` `-` `` # WRITE YOUR BRILLIANT CODE HERE`` `5` `4` ``if __name__ == "__main__":`` `6` `5` `` # driver code, do not modify`` `7` `6` `` matrix = [[int(x) for x in input().split()] for _ in range(int(input()))]``