题目描述

Why did the cow cross the road? Well, one reason is that Farmer John's farm simply has a lot of roads, making it impossible for his cows to travel around without crossing many of them.

FJ's farm is arranged as an $N \times N$ square grid of fields ($3 \leq N \leq 100$), with a set of $N-1$ north-south roads and $N-1$ east-west roads running through the interior of the farm serving as dividers between the fields. A tall fence runs around the external perimeter, preventing cows from leaving the farm. Bessie the cow can move freely from any field to any other 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 $T$ units of time to cross a road ($0 \leq T \leq 1,000,000$).

One day, FJ invites Bessie to visit his house for a friendly game of chess. Bessie starts out in the north-west corner field and 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 including possibly the final field in which FJ's house resides). Some fields are grassier than others, so the amount of time required for stopping to eat depends on the field in which she stops.

Please help Bessie determine the minimum amount of time it will take to reach FJ's house.

输入格式

The first line of input contains $N$ and $T$. The next $N$ lines each contain $N$ positive integers (each at most 100,000) describing the amount of time required to eat grass in each field. The first number of the first line is the north-west corner.

输出格式

Print the minimum amount of time required for Bessie to travel to FJ's house.

题目大意

题目描述

奶牛为什么要过马路？其中一个原因是 Farmer John 的农场有很多道路，使得他的奶牛在四处走动时不可避免地要穿过许多道路。

FJ 的农场被安排成一个 $N \times N$ 的方形网格田地（$3 \leq N \leq 100$），其中有 $N-1$ 条南北向的道路和 $N-1$ 条东西向的道路穿过农场内部，作为田地之间的分隔。农场外部有一圈高高的围栏，防止奶牛离开农场。奶牛 Bessie 可以自由地从任何田地移动到相邻的田地（北、东、南或西），只要她在穿过分隔两块田地的道路时小心地左右看看。她穿过一条道路需要花费 $T$ 单位时间（$0 \leq T \leq 1,000,000$）。

有一天，FJ 邀请 Bessie 去他家进行一场友好的国际象棋比赛。Bessie 从西北角的田地出发，而 FJ 的家在东南角的田地，因此 Bessie 需要走很长一段路。由于她在路上会感到饥饿，她会在每经过第三个田地时停下来吃草（不包括她的起始田地，但可能包括最终到达的 FJ 家的田地）。有些田地的草比其他田地更茂盛，因此停下来吃草所需的时间取决于她停下的田地。

请帮助 Bessie 确定她到达 FJ 家所需的最少时间。

输入格式

输入的第一行包含 $N$ 和 $T$。接下来的 $N$ 行每行包含 $N$ 个正整数（每个数不超过 100,000），描述了每个田地中吃草所需的时间。第一行的第一个数是西北角的田地。

输出格式

输出 Bessie 到达 FJ 家所需的最少时间。

说明/提示

这个例子的最优解是向东移动 3 个方格（吃“10”），然后向南移动两次，向西移动一次（吃“5”），最后向南和向东移动到目的地。

4 2
30 92 36 10
38 85 60 16
41 13 5 68
20 97 13 80

31

提示

The optimal solution for this example involves moving east 3 squares (eating the "10"), then moving south twice and west once (eating the "5"), and finally moving south and east to the goal.