暗区突围与三角洲行动

题目背景

你是一名特种部队队员，被派遣执行一项特殊的任务——从暗区突围并成功到达三角洲行动基地。暗区是一个由 n 行 m 列的网格组成的区域，其中每个格子可能包含障碍物或者提供额外的能量。你的任务是从暗区的左上角（起点）出发，到达右下角（终点），同时尽量使用最少的能量。

你只能向右或向下移动。如果移动到一个格子，格子中有一个障碍物，你将无法通过该格子。如果格子中提供额外的能量，你可以选择吸收这部分能量（每次吸收能量会减少你消耗的能量）。你需要计算从起点到终点的最小能量消耗

题目描述

暗区是一个由 n 行 m 列的网格组成的区域，其中每个格子可能包含障碍物或者提供额外的能量。你的任务是从暗区的左上角（起点）出发，到达右下角（终点），同时尽量使用最少的能量。你只能向右或向下移动。如果移动到一个格子，格子中有一个障碍物，你将无法通过该格子。如果格子中提供额外的能量，你可以选择吸收这部分能量（每次吸收能量会减少你消耗的能量）。你需要计算从起点到终点的最小能量消耗

输入格式

第一行包含两个整数 n 和 m，分别表示暗区的行数和列数。 接下来的 n 行，每行包含 m 个整数，表示每个格子的能量值。如果格子的能量值为 -1，表示该格子有障碍物；如果格子的能量值为正整数，表示该格子可以提供额外的能量。

输出格式

输出一个整数，表示从起点到终点的最小能量消耗。如果无法从起点到达终点，则输出 -1。

提示

样例输入

3 3

0 1 2

-1 3 1

1 0 0

样例输出

2

样例解释

暗区是一个 3x3 的网格。

起点在左上角 (0, 0)，终点在右下角 (2, 2)。

从起点到终点的路径可以是 (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2)。

这条路径的能量消耗计算如下：

初始能量消耗为 0。

移动到 (0, 1)，能量消耗增加 1，变为 1。

移动到 (0, 2)，能量消耗增加 2，变为 3。

移动到 (1, 2)，吸收能量 1，能量消耗变为 2。

移动到 (2, 2)，吸收能量 0，能量消耗不变，为 2。

数据范围与提示

对于 30% 的数据，1 ≤ n, m ≤ 10。

对于 100% 的数据，1 ≤ n, m ≤ 100，格子的能量值范围在 -1 到 100 之间。

审核组放假了，大家帮我看一下行吗？