字母收集
题号:NC221826
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

有一个 的矩形方阵,每个格子上面写了一个小写字母。
小红站在矩形的左上角,她每次可以向右或者向下走,走到某个格子上就可以收集这个格子的字母。
小红非常喜欢 "love" 这四个字母。她拿到一个 l 字母可以得 4 分,拿到一个 o 字母可以得 3 分,拿到一个 v 字母可以得 2 分,拿到一个 e 字母可以得 1 分。
她想知道,在最优的选择一条路径的情况下,她最多能获取多少分?

输入描述:


接下来的 行 每行一个长度为 的、仅有小写字母构成的字符串,代表矩形方阵。

输出描述:

小红最大可能的得分。

示例1

输入

复制
3 2
ab
cd
ef

输出

复制
1

说明

选择下、下、右)这条路径即可,可以收集到 acef 这四个字母各一次,获得 0+0+1+0=1 分。  
示例2

输入

复制
2 3
lle
ove

输出

复制
11