Tại sao con bò băng qua đường? Một lý do là trang trại của Farmer John có quá nhiều đường, khiến đàn bò của ông không thể đi lại mà không phải băng qua nhiều con đường.

Trang trại của FJ được bố trí thành một lưới ô vuông \(N \times N\) gồm các cánh đồng (\(3 \leq N \leq 100\)), với \(N-1\) con đường theo hướng bắc-nam và \(N-1\) con đường theo hướng đông-tây chạy xuyên qua bên trong trang trại, đóng vai trò phân chia các cánh đồng. Một hàng rào cao chạy quanh chu vi bên ngoài, ngăn bò rời khỏi trang trại. Bò Bessie có thể tự do di chuyển từ bất kỳ cánh đồng nào sang một cánh đồng kề nó (về phía bắc, đông, nam hoặc tây), miễn là nó cẩn thận nhìn cả hai phía trước khi băng qua con đường ngăn cách hai cánh đồng. Nó mất \(T\) đơn vị thời gian để băng qua một con đường (\(0 \leq T \leq 1,000,000\)).

Một ngày nọ, FJ mời Bessie đến nhà chơi một ván cờ thân mật. Bessie bắt đầu ở cánh đồng góc tây bắc, còn nhà của FJ nằm ở cánh đồng góc đông nam, nên nó phải đi bộ một quãng khá dài. Vì bị đói dọc đường, cứ đến cánh đồng thứ ba mà mình ghé qua, nó lại dừng lại để ăn cỏ (không tính cánh đồng xuất phát, nhưng có thể tính cánh đồng cuối cùng nơi nhà FJ tọa lạc). Một số cánh đồng có nhiều cỏ hơn những cánh đồng khác, vì vậy thời gian dừng lại ăn phụ thuộc vào cánh đồng nơi nó dừng chân.

Hãy giúp Bessie xác định thời gian ít nhất để đến nhà FJ.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(T\). Mỗi dòng trong \(N\) dòng tiếp theo chứa \(N\) số nguyên dương (mỗi số không quá 100.000), mô tả thời gian cần để ăn cỏ tại từng cánh đồng. Số đầu tiên của dòng đầu tiên ứng với góc tây bắc.

Dữ liệu ra

In ra thời gian ít nhất để Bessie đến nhà FJ.

Ví dụ

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

31

Nguồn

USACO 2017 February Contest, Gold — Why Did the Cow Cross the Road. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=717