class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        W = len(dungeon)
        H = len(dungeon[0])

        max_hp_needed = -sum(
            dungeon[x][y]
            for x in range(W)
            for y in range(H)
            if dungeon[x][y] < 0
        ) + 1

        if max_hp_needed == 1:
            return 1

        b, e = 1, max_hp_needed + 1
        ans = max_hp_needed
        while b < e:
            m = (b + e) // 2
            if self.canTraverse(dungeon, m):
                ans = m
                e = m
            else:
                b = m + 1
        return ans

    def canTraverse(self, dungeon: List[List[int]], hp: int) -> bool:
        W = len(dungeon)
        H = len(dungeon[0])

        prev_hp_row = [- hp - 1] * (W + 1)
        cur_hp_row = [- hp - 1] * (W + 1)

        # Essentially this makes it as if we'll enter the dungeon
        # from a room above the top-left room.
        prev_hp_row[0] = hp
        for y in range(H):
            for x in range(W):
                best_starting_hp = max(
                    prev_hp_row[x],
                    cur_hp_row[x - 1],
                )
                cur_hp_row[x] = best_starting_hp

                # If you're dead stay dead
                if best_starting_hp <= 0:
                    continue
                cur_hp_row[x] += dungeon[x][y]

            if y == H - 1:
                return cur_hp_row[W - 1] > 0

            prev_hp_row, cur_hp_row = cur_hp_row, prev_hp_row

        return False