#include using namespace std; int main() { int64_t N, M; cin >> N >> M; vector> A(N, vector(M)); for (int64_t i = 0; i < N; i++) { for (int64_t j = 0; j < M; j++) { cin >> A[i][j]; } } // dp[i][j] := i回目まで行けるようにしたとき、直前ではj番目を取り壊したときの最小コスト vector> dp(N + 1, vector(M, LLONG_MAX / 2)); for (int64_t i = 0; i < N - 1; i++) { // ここでの最小コスト vector min_from_l(M, LLONG_MAX / 2); vector min_from_r(M, LLONG_MAX / 2); min_from_l[0] = dp[i][0]; min_from_r[M - 1] = dp[i][M - 1]; for (int64_t j = 1; j < M; j++) { min_from_l[j] = min(dp[i][j], min_from_l[j - 1]); } for (int64_t j = M - 2; j >= 0; j--) { min_from_r[j] = min(dp[i][j], min_from_r[j + 1]); } for (int64_t j = 0; j < M; j++) { // jを開けていて、そこから直接繋ぐ dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + A[i + 1][j]); // j以外を開けていて、そこから2段繋ぐ const int64_t min_l = (j == 0 ? LLONG_MAX : min_from_l[j - 1]); const int64_t min_r = (j == M - 1 ? LLONG_MAX : min_from_r[j + 1]); const int64_t other_min = (i == 0 ? 0 : min(min_l, min_r)); dp[i + 1][j] = min(dp[i + 1][j], other_min + A[i][j] + A[i + 1][j]); } } if (N == 1) { cout << 0 << endl; return 0; } cout << *min_element(dp[N - 1].begin(), dp[N - 1].end()) << endl; }