P15226 [SWERC 2017] Burglary

皇家厨房的巨型糖果墙用于存放……没错，糖果棒。这些糖果棒被放置在 $N$ 个等长架子的罐子里。架子从地面向上垂直排列，且它们的最左和最右边缘水平对齐。每个架子被划分为 $M$ 个等大小的槽，每个槽可以是空的，也可以被一个罐子占据。一个罐子包含 1 到 9 根糖果棒。 每个架子通过一个或多个垂直梯子与正下方的架子（或地面，对于最底层的架子）相连。一个梯子连接一个槽与下方架子对应的槽，或连接到地面。在任何给定槽的正下方最多有一个梯子。 最顶层的架子不包含任何罐子，但紧挨其上是一个巨大的敞开窗户，通向皇家厨房的屋顶。Mini-Fierce-And-Hungry Bandit 惊人地通过这个顶部窗户进入了皇家厨房，现在计划进行一次大规模的糖果棒盗窃。更准确地说，他打算在墙上进行一次有趣且有利可图的“往返旅行”，即： - 从最顶层的架子开始； - 向下移动 0 个或多个架子，可能直到到达地面； - 然后再次向上移动，通过顶部窗户优雅退出； 当然，在此过程中尽可能多地抓取糖果棒。 然而，强盗面临的主要问题是：他不能进入包含糖果罐的槽超过一次，因为这会触发可怕的糖果警报。 你的任务：帮助强盗仔细计划他在糖果墙上的往返旅行，以最大化抓取的糖果棒数量，而不触发任何警报。

第一行包含两个整数：$N$（架子数量）和 $M$（每个架子的槽数），以空格分隔。接下来的 $2N$ 行每行包含长度为 $M$ 的字符串，以 ASCII 艺术形式描述架子和梯子的配置： - 对于 $1 \leq k \leq N$，第 $2k$ 行包含字符 ‘-’、‘1’、……、‘9’，其中数字 $x$ 表示一个装有 $x$ 根糖果棒的罐子，而 ‘-’ 表示空槽。 - 对于 $1 \leq k \leq N$，第 $2k+1$ 行包含字符 ‘.’ 和 ‘|’，其中 ‘|’ 表示梯子，‘.’ 表示空的墙壁空间。

输出包含一行一个整数，表示强盗在不触发任何警报的情况下可以收集的最大糖果棒数量。

#### 样例解释 :::align{center}  ::: #### 注意 - 梯子端点对应的槽可能包含罐子。 - 一个槽可以通过在架子上行走（从左到右或从右到左）进入，或者通过到达梯子的端点进入。如果使用了梯子，则梯子端点对应的槽必然被进入。 - 最顶层架子和地面上没有糖果罐。 ### 数据范围 - $1 \leq N \leq 1000$； - $1 \leq M \leq 500$； - 任何架子正下方有 1 到 10 个梯子。 翻译由 DeepSeek 完成