409441: GYM103561 F Summit Sunset

In preparation for Valentine's Day, Yaroslav is searching for the perfect date. He has decided to take his partner Rostislav hiking to the top of a local mountain to view the sunset.

The hiking area is described as a $$$N \times N$$$ grid of height values $$$h_{i,j}$$$ and the two will be starting at $$$(0, 0)$$$, traveling to the peak (maximal height) within the area.

Yaroslav wants to minimize the total energy expended during their hike, instead preferring to stare into Rostislav's dreamy eyes. Ascending or descending by $$$d$$$ costs $$$d^2$$$ energy. Since they are still novice hikers, they can only travel between grid cells that share a side.

Given the height grid of the surrounding land, help Yaroslav find the easiest hike and make their sunset date perfect.

The first line contains a single integer $$$1 \leq N \leq 500$$$

The $$$i+1$$$th line contain $$$N$$$ integers $$$1 \leq h_{i,j} \leq 1000$$$

A single integer, denoting the minimum energy spent to climb to the peak.

3
1 2 4
4 5 6
4 8 7

11

There will be a unique peak.