package main

func calculateMinimumHP(dungeon [][]int) int {
	m, n := len(dungeon), len(dungeon[0]) // Reverse DP
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	dp[m-1][n-1] = maxInt(1, 1-dungeon[m-1][n-1])
	for i := m - 2; 0 <= i; i-- {
		dp[i][n-1] = maxInt(1, dp[i+1][n-1]-dungeon[i][n-1])
	}
	for j := n - 2; 0 <= j; j-- {
		dp[m-1][j] = maxInt(1, dp[m-1][j+1]-dungeon[m-1][j])
	}
	for i := m - 2; 0 <= i; i-- {
		for j := n - 2; 0 <= j; j-- {
			need := minInt(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]
			dp[i][j] = maxInt(1, need)
		}
	}
	return dp[0][0]
}

// func main() {
// 	println(calculateMinimumHP([][]int{
// 		{1, -3, 3},
// 		{0, -2, 0},
// 		{-3, -3, -3}}), 3)
// }