皇家厨房里的巨大糖果墙被用来存放……嗯，糖果棒。这些糖果棒被装在罐子里，放置在 $N$ 个等长的架子上。这些架子从地面向上垂直排列，并且在最右侧和最左侧的边缘上完美地水平对齐。每个架子被划分为 $M$ 个等大的槽位，槽位可以是空的，也可以放有一个罐子。一个罐子里装有 1 到 9 根糖果棒。

每个架子通过一个或多个垂直梯子与正下方的架子（或最底层的地面）相连。梯子将一个槽位与下方架子上的对应槽位或地面相连。在任何给定的槽位下方最多只有一个梯子。

最顶层的架子上没有任何罐子，但在它上方有一个通往皇家厨房屋顶的巨大敞开窗户。迷你凶猛贪婪大盗（Mini-Fierce-And-Hungry Bandit）出人意料地通过这个顶部的窗户潜入了皇家厨房，现在计划进行一场大规模的糖果棒盗窃。更确切地说，他打算在墙上进行一次有趣且有利可图的“往返旅行”，即： 从最顶层的架子出发； 向下移动 0 个或多个架子，可能直到到达地面； * 然后再向上移动，回到顶部的窗户并优雅地离开； 在这次旅行中，他当然要尽可能多地抓取糖果棒。

然而，大盗面临的主要问题是，他不能进入同一个装有糖果罐的槽位超过一次，因为这会触发可怕的糖果警报。

你的任务是：帮助大盗仔细规划他在糖果墙上的往返路线，以便在不触发任何警报的情况下，最大化他能抓取的糖果棒数量。

输入格式

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

数据范围

• $1 \le N \le 1000$
• $1 \le M \le 5000$
• 任何架子下方有 1 到 10 个梯子。

输出格式

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

说明

• 梯子端点对应的槽位可能包含罐子。
• 进入一个槽位可以通过在架子上行走（从左到右或从右到左），或者通过到达梯子的端点。如果使用了梯子，则必须进入梯子端点对应的槽位。
• 最顶层的架子和地面上没有糖果罐。

样例

输入格式 1

5 20
--------------------
.|.....|...|......|.
1-1--1115-3-1-1--1-1
....|.........|.....
---1-11-1-11---1--3-
.......|.........|..
-7----9-4-----------
..|.................
--------9-----------
.|.................|

输出格式 1

38