Minimal Grid Difficulty Coverage

You are given a grid of size n by m where each cell contains a positive integer representing the difficulty to traverse that cell. A robot must cover the entire grid by visiting each cell exactly once. From any cell, the robot can move to any adjacent cell in one of the four directions (up, down, left, or right).

The task is to determine the minimal total difficulty of covering the grid. Mathematically, if the robot follows a path that visits every cell exactly once, and if the difficulty of a cell at position \((i,j)\) is denoted by \(a_{ij}\), then the total difficulty is given by:

\(\text{Total Difficulty} = \sum_{(i,j) \in \text{path}} a_{ij}\)

Your goal is to find the path which minimizes this total difficulty and output that minimum value.

inputFormat

The first line of input contains two integers \(n\) and \(m\) representing the number of rows and columns respectively.

This is followed by \(n\) lines, each containing \(m\) space-separated positive integers representing the grid.

outputFormat

Output a single integer which is the minimal total difficulty to cover the grid by visiting every cell exactly once.

2 2
1 2
3 4

10