ac

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static int mod=(int)Math.pow(10,9)+7;

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] arr = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                arr[i][j] = sc.nextInt();
            }
        }

        int dp[] = new int[m];
        dp[0] = arr[0][0];
        for(int i=1;i<m;i++){
            dp[i] = arr[0][i] + dp[i-1];
        }
        for(int i=1;i<n;i++){
            for(int j=0;j<m;j++){
                if(j == 0){
                    dp[j] = dp[j] + arr[i][j];
                }else {
                    dp[j] = Math.min(dp[j] + arr[i][j], dp[j-1] + arr[i][j]);
                }
            }
        }
        int ans = dp[m-1];
        System.out.println(ans);
    }
}
/*
4 4
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0

12
 */

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static int mod=(int)Math.pow(10,9)+7;

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] arr = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                arr[i][j] = sc.nextInt();
            }
        }
        int ans;
        if(m <= n){
            ans = getAnsRow(arr, n, m);
        }else {
            ans = getAnsColumn(arr, n, m);
        }
        System.out.println(ans);
    }

    // 消耗空间O(m)
    static int getAnsRow(int[][] arr, int n, int m){
        int dp[] = new int[m];
        dp[0] = arr[0][0];
        for(int i=1;i<m;i++){
            dp[i] = arr[0][i] + dp[i-1];
        }
        for(int i=1;i<n;i++){
            for(int j=0;j<m;j++){
                if(j == 0){
                    dp[j] = dp[j] + arr[i][j];
                }else {
                    dp[j] = Math.min(dp[j] + arr[i][j], dp[j-1] + arr[i][j]);
                }
            }
        }
        int ans = dp[m-1];
        return ans;
    }

    // 消耗空间O(n)
    static int getAnsColumn(int[][] arr, int n, int m){
        int dp[] = new int[n];
        dp[0] = arr[0][0];
        for(int i=1;i<n;i++){
            dp[i] = arr[i][0] + dp[i-1];
        }
        for(int j=1;j<m;j++){
            for(int i=0;i<n;i++){
                if(i == 0){
                    dp[i] = dp[i] + arr[i][j];
                }else {
                    dp[i] = Math.min(dp[i] + arr[i][j], dp[i-1] + arr[i][j]);
                }
            }
        }
        int ans = dp[n-1];
        return ans;
    }
}
/*
4 4
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0

12
 */