#include using namespace atcoder; // using mint = modint1000000007; using mint = modint998244353; // using mint = modint;//mint::set_mod(MOD); // const long long MOD = 1000000007; const long long MOD = 998244353; #include #define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) #define repeq(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); i++) #define repreq(i, a, b) for (ll i = (ll)(a); i >= (ll)(b); i--) #define each(a, b) for (auto &(a) : (b)) #define endl '\n' // fflush(stdout); #define cYes cout << "Yes" << endl #define cNo cout << "No" << endl #define sortr(v) sort(v, greater<>()) #define pb push_back #define mp make_pair #define mt make_tuple #define tget(a, b) get(a) #define FI first #define SE second #define ALL(v) (v).begin(), (v).end() #define INFLL 3000000000000000100LL #define INF 1000000100 #define PI acos(-1.0L) #define TAU (PI * 2.0L) using namespace std; typedef long long ll; typedef pair Pll; typedef tuple Tlll; typedef vector Vi; typedef vector VVi; typedef vector Vl; typedef vector VVl; typedef vector VVVl; typedef vector VTlll; typedef vector Vm; typedef vector VVm; typedef vector Vs; typedef vector Vd; typedef vector Vc; typedef vector Vb; typedef vector VPll; typedef priority_queue PQl; typedef priority_queue, greater> PQlr; /* print */ template ostream &operator<<(ostream &os, const vector &V) { int N = V.size(); if (N == 0) { os << endl; return os; } rep(i, 0, N - 1) { os << V[i] << ' '; } os << V[N - 1] << endl; return os; } template ostream &operator<<(ostream &os, const vector> &V) { int N = V.size(); rep(i, 0, N) os << V[i]; return os; } template ostream &operator<<(ostream &os, pair const &P) { os << P.FI << ' ' << P.SE; return os; } ostream &operator<<(ostream &os, mint const &M) { os << M.val(); return os; } /* useful */ template void Vin(vector &v) { int n = v.size(); rep(i, 0, n) cin >> v[i]; } template int SMALLER(vector &a, T x) { return lower_bound(a.begin(), a.end(), x) - a.begin(); } template int orSMALLER(vector &a, T x) { return upper_bound(a.begin(), a.end(), x) - a.begin(); } template int BIGGER(vector &a, T x) { return a.size() - orSMALLER(a, x); } template int orBIGGER(vector &a, T x) { return a.size() - SMALLER(a, x); } template int COUNT(vector &a, T x) { return upper_bound(ALL(a), x) - lower_bound(ALL(a), x); } template bool chmax(T &a, S b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, S b) { if (a > b) { a = b; return 1; } return 0; } template void press(T &v) { v.erase(unique(ALL(v)), v.end()); } template vector zip(vector b) { pair p[b.size() + 10]; int a = b.size(); vector l(a); for (int i = 0; i < a; i++) p[i] = mp(b[i], i); sort(p, p + a); int w = 0; for (int i = 0; i < a; i++) { if (i && p[i].first != p[i - 1].first) w++; l[p[i].second] = w; } return l; } template vector vis(vector &v) { vector S(v.size() + 1); rep(i, 1, S.size()) S[i] += v[i - 1] + S[i - 1]; return S; } ll dem(ll a, ll b) { return ((a + b - 1) / (b)); } ll dtoll(double d, int g) { return round(d * pow(10, g)); } const double EPS = 1e-10; void init() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(12); } // do {} while (next_permutation(ALL(vec))); // for (auto p : se ) {} /********************************** START **********************************/ template struct graph { struct edge { int to; T cost; }; int N; vector> G; vector dist; vector prever; graph(int n) { init(n); } T inf() { if (is_same_v) return T(INF); else return T(INFLL); } T zero() { return T(0); } void init(int n) { N = n; G.resize(N); dist.resize(N, inf()); } void add_edge(int s, int t, T cost) { edge e; e.to = t, e.cost = cost; G[s].push_back(e); } void dijkstra(int s) { rep(i, 0, N) dist[i] = inf(); prever = vector(N, -1); dist[s] = zero(); priority_queue, vector>, greater>> q; q.push(mp(zero(), s)); while (!q.empty()) { int now; T nowdist; tie(nowdist, now) = q.top(); q.pop(); if (dist[now] < nowdist) continue; for (auto e : G[now]) { if (dist[e.to] > dist[now] + e.cost) { prever[e.to] = now; dist[e.to] = dist[now] + e.cost; q.push(mp(dist[e.to], e.to)); } } } } vector get_path(int t) { // tへの最短路構築 if (dist[t] >= inf()) return {-1}; vector path; for (; t != -1; t = prever[t]) { path.push_back(t); } reverse(path.begin(), path.end()); return path; } }; void sol() { int h, w; cin >> h >> w; VVl a(h, Vl(w)); rep(i, 0, h) rep(j, 0, w) cin >> a[i][j]; if (h == 1) { cout << 0 << endl; return; } graph gr(h * w + 2010); int s = h * w + 2000; int t = h * w + 2001; rep(i, 0, w) { gr.add_edge(s, i, 0); // gr.add_edge(i + w * (h - 1), t, 0); } Vl yo(h); rep(i, 0, h) yo[i] = h * w + i; rep(i, 0, h) { rep(j, 0, w) { int nw = w * i + j; int ue = nw + w; if (ue < h * w) { gr.add_edge(nw, ue, a[i][j]); } else { gr.add_edge(nw, t, a[i][j]); } gr.add_edge(nw, yo[i], a[i][j]); gr.add_edge(yo[i], nw, 0); } } gr.dijkstra(s); cout << gr.dist[t] << endl; } int main() { init(); int q = 1; // cin >> q; while (q--) sol(); return 0; }