ac

游戏的规则如下:
      1）骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。
      2）地图中每个位置的值代表骑士要遭遇的事情。如果是负数，说明此处有怪兽，要让骑士损失血量。如果是非负数，代表此处有血瓶，能让骑士回血。
      3）骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于1。为了保证骑土能见到公主，初始血量至少是多少?

import java.util.Scanner;


public class Main {

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

    public static void main(String[] args) {
        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(n< m) {
            ans = getAnsByColumns(arr, n, m);
        }else {
            ans = getAnsByRows(arr, n, m);
        }
        System.out.print(ans);
    }

    static int getAnsByRows(int[][] arr, int n, int m){
        // 一行一行来
        int[] dp = new int[m];
        // 走到(i,j)位置,需要具备的血量
        if(arr[n-1][m-1] >= 0){
            dp[m-1] = 1;
        }else {
            dp[m-1] = 1 - arr[n-1][m-1];
        }
        // 往左
        for(int i=m-2;i>=0;i--){
            dp[i] = Math.max(1, dp[i+1] - arr[n-1][i]);
        }
        for(int i=n-2;i>=0;i--){
            for(int j=m-1;j>=0;j--){
                if(j == m-1) {
                    int down = Math.max(1, dp[j] - arr[i][j]);
                    dp[j] = down;
                }else {
                    int right = Math.max(1, dp[j+1] - arr[i][j]);
                    int down = Math.max(1, dp[j] - arr[i][j]);
                    dp[j] = Math.min(down, right);
                }
            }
        }
        return dp[0];
    }

    static int getAnsByColumns(int[][] arr, int n, int m){
        // 一列一列
        int[] dp = new int[n];
        // 走到(i,j)位置,需要具备的血量
        if(arr[n-1][m-1] >= 0){
            dp[n-1] = 1;
        }else {
            dp[n-1] = 1 - arr[n-1][m-1];
        }
        // 往上
        for(int i=n-2;i>=0;i--){
            dp[i] = Math.max(1, dp[i+1] - arr[i][m-1]);
        }
        for(int j=m-2;j>=0;j--){
            for(int i=n-1;i>=0;i--){
                if(i == n-1) {
                    int right = Math.max(1, dp[i] - arr[i][j]);
                    dp[i] = right;
                }else {
                    int right = Math.max(1, dp[i] - arr[i][j]);
                    int down = Math.max(1, dp[i+1] - arr[i][j]);
                    dp[i] = Math.min(down, right);
                }
            }
        }
        return dp[0];
    }

}
/*
3 3
-2 -3 3
-5 -10 1
0 30 -5

7
*/

import java.util.Scanner;


public class Main {

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

    static int getNeed(int val){
        if(val >= 1){ // 大于等于1的 need = 0, 其它都是需要need的
            return 0;
        }else {
            return 1 - val;
        }
    }

    public static void main(String[] args) {
        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();
            }
        }

        // 走到(i,j)位置,需要具备的血量
        int[][] dp = new int[n][m];
        if(arr[n-1][m-1] >= 0){
            dp[n-1][m-1] = 1;
        }else {
            dp[n-1][m-1] = 1 - arr[n-1][m-1];
        }
        // 往上
        for(int i=n-2;i>=0;i--){
            dp[i][m-1] = Math.max(1, dp[i+1][m-1] - arr[i][m-1]);
        }
        // 往左
        for(int i=m-2;i>=0;i--){
            dp[n-1][i] = Math.max(1, dp[n-1][i+1] - arr[n-1][i]);
        }
        for(int i=n-2;i>=0;i--){
            for(int j=m-2;j>=0;j--){
                int down =  Math.max(1, dp[i][j+1] - arr[i][j]);
                int right =  Math.max(1, dp[i+1][j] - arr[i][j]);
                dp[i][j] = Math.min(down, right);
            }
        }

        System.out.print(dp[0][0]);
    }


}
/*
3 3
-2 -3 3
-5 -10 1
0 30 -5

7
*/