Why Did the Cow Cross the Road (Gold)#10538
FJ's farm is arranged as an n \times n square grid of fields, with n - 1 north-south roads and n - 1 east-west roads running through the interior of the farm and separating adjacent fields. A tall fence runs around the perimeter of the farm, preventing cows from leaving. Bessie the cow can move freely from any field to any adjacent field (north, east, south, or west), as long as she carefully looks both ways before crossing the road separating the two fields. It takes her units of time to cross a road.
One day, FJ invites Bessie to visit his house for a friendly game of chess. Bessie starts in the north-west corner field, while FJ's house is in the south-east corner field, so Bessie has quite a walk ahead of her. Since she gets hungry along the way, she stops at every third field she visits to eat grass (not including her starting field, but possibly including the final field where FJ's house is located). Some fields are grassier than others, so the amount of time Bessie needs to stop and eat depends on the field where she stops.
Please help Bessie determine the minimum amount of time it will take her to reach FJ's house.
The first line contains n~(3 \le n \le 100) and t~(0 \le t \le 10^6). The next lines each contain positive integers (each at most 10^5) describing the amount of time required to eat grass in each field. The first number in the first line corresponds to the north-west corner field.
Print the minimum amount of time required for Bessie to reach FJ's house.
In this example, the optimal solution involves moving east squares and eating the units of grass, then moving south twice and east once and eating the units of grass, and finally moving south and east to reach the goal.
Example 1