题目描述

有一个大小为n × m的地图，地图上每个格子都是红色或紫色的，每个格子都有一个价值为aj的宝藏，小红只能挖红色格子上的宝藏，小紫只能挖紫色格子上的宝藏。

小红和小紫初始在地图左上角，她们只能同时向下或向右走，她们挖宝有以下限制:

1. 有的格子可以跳过不挖。
2. 对于同一个人，不能连续挖两个相邻的格子。

她们想知道走到地图右下角—共能获得的宝藏的最大价值和是多少。

输入描述

第—行输入两个整数n, m。

接下来n行，每行输入m个整数aj表示地图上每个点的价值。

接下来n行，每行输入一个长度为m的只由'R'和'P'组成的字符串表示地图每个格子的颜色，'R'代表格子为红色，'P'代表格子为紫色。

1 <= n, m <= 1000;

1 ≤ aj ≤ 109。

输出描述

输出一个整数表示答案。

输入示例

3 3
3 2 1
3 3 3
1 2 3
RPR
PRP
RPR

输出示例

15

提示信息

第0步，小红挖(1, 1)格子，获得价值为3的宝藏。第1步，小红和小紫往下走，小紫挖(2, 1)格子，获得价值为3的宝藏。第2步，小红和小紫往右走，小红挖(2, 2)格子，获得价值为3的宝藏。第3步，小红和小紫往右走，小紫挖(2, 3)格子，获得价值为3的宝藏。第4步，小红和小紫往下走，小红挖(3, 3)格子，获得价值为3的宝藏。总共获得了价值为3 + 3 + 3 + 3 + 3 = 15的宝藏。

时间限制：c/c++：2s；java/go：7s；其他语言：13s。