The Cow Crossing Challenge

Bessie the cow is trying to reach Farmer John's house on the opposite corner of his farm. The farm is organized as an \(N \times N\) square grid of fields with \(N-1\) north-south roads and \(N-1\) east-west roads dividing the fields. A tall fence surrounds the outer perimeter so Bessie cannot leave the farm. She can move north, south, east, or west between adjacent fields, but must cross a road between each adjacent field and it takes her \(T\) units of time to cross any road.

Bessie starts at the north-west corner field and needs to reach FJ's house at the south-east corner field. However, she gets hungry along the way so she stops at every third field she visits (the starting field is not counted, though the final field may count if it is the third visit). Each time she stops, she spends extra time eating grass. Different fields require different amounts of time to eat, and these are given as an \(N \times N\) matrix. More formally, define the count of fields visited (excluding the starting field). Every time Bessie takes a step, increment the counter; if the new counter is divisible by 3, she pays an extra cost equal to the grass-eating time for that field.

Your task is to compute the minimum amount of time for Bessie to travel from the starting field to FJ's house, including both the time to cross roads and any grass eating time incurred.

inputFormat

The first line contains two integers \(N\) and \(T\) where \(3 \leq N \leq 100\) and \(0 \leq T \leq 10^6\). Each of the next \(N\) lines contains \(N\) space-separated non-negative integers. The \(j\)-th integer in the \(i\)-th line represents the extra grass eating time required if Bessie stops in the field at row \(i\) and column \(j\) (with rows numbered from north to south and columns from west to east).

outputFormat

Output a single integer representing the minimum total time required for Bessie to reach FJ's house at the south-east corner field.

sample

3 2
1 2 3
4 5 6
7 8 9

16