the demon capture princess imprison bottomright corner dungeon the dungeon consist m x n room lay 2D grid our valiant knight initially position topleft room fight way dungeon rescue princessthe knight initial health point represent positive integer if point health point drop 0 die immediatelysome room guard demon represent negative integer knight lose health enter room room represent 0 contain magic orb increase knight health represent positive integersTo reach princess quickly possible knight decides rightward downward stepreturn knight minimum initial health rescue princessnote room contain threat powerup room knight enter bottomright room princess imprison Example 1input dungeon 233510110305output 7explanation the initial health knight 7 follow optimal path right right DOWN DOWNExample 2Input dungeon 0output 1 Constraintsm dungeonlengthn dungeonilength1 m n 2001000 dungeonij 1000