Minimizing Snack Expenses at the Shrine Fair

At a bustling shrine fair held in a city, there is an H×W grid of booths arranged in H rows (north‐to‐south) and W columns (west‐to‐east). The booth in the i-th row from the north and the j-th column from the west is denoted by \((i,j)\).

The protagonist starts at booth \((1,1)\) and must travel to booth \((H,W)\) by moving only east or south. Note that the booths at \((1,1)\) and \((H,W)\) as well as all booths immediately adjacent in the four cardinal directions (north, south, east, and west) to these positions are closed (i.e. not operating). Other booths in the grid might also be closed. For an open booth, a nonnegative integer is given representing the cost to buy its snack; a closed booth is marked by \(-1\).

The protagonist is a self‐confessed foodie. Whenever she reaches a booth, regardless of whether that booth is open or closed, she first checks the booth. If the booth is open and its snack has not yet been purchased, she buys it – incurring the booth’s cost. Then, regardless of the booth’s status, she finds the aroma of snacks from all its directly adjacent (north, south, east, and west) booths so irresistible that if among these adjacent booths there are \(r\) open booths whose snacks have not yet been purchased (\(r \ge 2\)), she is forced to buy the snacks from \(r-1\) of them. In other words, from the set of unbought adjacent open booths, she may choose exactly one booth to skip (or if there is only one such booth, none are bought), and she must purchase the snacks from all the others. Note that if a booth’s snack is purchased (either by direct visit or forced purchase) it will not be bought again later even if encountered a second time.

The protagonist, though a glutton, has limited pocket money, and she cannot help but buy snacks. She wonders: What is the minimum total cost she will incur by the time she reaches \((H,W)\) if she optimizes both her route (always moving east or south) and the choices of which adjacent booth to skip during the forced purchases? (All formulae below are rendered in \(\LaTeX\); for example, the grid dimensions are given by \(H\) and \(W\), and positions are denoted by \((i,j)\).)

Input Format: The first line contains two integers \(H\) and \(W\). The following \(H\) lines each contain \(W\) integers. For an open booth, a nonnegative integer indicates the cost of its snack; a closed booth is denoted by \(-1\). It is guaranteed that the booths at \((1,1)\) and \((H,W)\) and all booths immediately adjacent to them (in the four directions) are closed.

Output Format: Output a single integer indicating the minimum total cost incurred.

inputFormat

The input begins with a line containing two integers \(H\) and \(W\). Then follow \(H\) lines, each containing \(W\) space‐separated integers. A value of \(-1\) indicates a closed booth, while a nonnegative integer indicates an open booth with that snack cost.

outputFormat

Output a single integer — the minimum total cost incurred by the protagonist by the time she reaches booth \((H,W)\).

sample

2 2
-1 5
7 -1

5