题号：NC200010
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
卡特莉发现了一个关于多米诺骨牌的谜题。
现在她的面前有一个n行m列的棋盘，棋盘上的每个格子有各自的权值，特别有趣的是，这些权值有正有负。
现在卡特莉要把若干个1×2或2×1的多米诺骨牌摆放在棋盘上，然后她就可以取得被骨牌覆盖的格子的权值。请注意骨牌之间不能有重叠部分，也不能摆放伸出棋盘外的骨牌。
正如你猜的那样，卡特莉想要尽可能多地得到权值，请你求出她可以得到的最大权值和。
出于对解密的热爱，卡特莉对棋盘上的格子可能会特殊的偏好。一些格子必定会被她摆放的骨牌覆盖。相反地，还有一些格子必定不会被她摆放的格子覆盖。
输入描述:
第一行输入一个T(1<=T<=1000)表示数据组数。接下来T组数据。对于每组数据，第一行输入一个n，m(1<=n,m<=50)，分别表示行列数。
保证对于超过的数据，max(n,m)<=10，保证这部分数据是随机生成的。
每个格子的权值绝对值小于等于1000。接下来输入n行m列的字符。
对于每个位置的字符：表示可以任意选择覆盖或者不覆盖。
表示该位置不能被覆盖。
表示该位置必须被覆盖。
接下来再输入n行m列个数字。
每个位置的数字表示这个位置格子的权值。
输出描述:
对于每组数据，请你输出卡特莉可以得到的最大权值。
如果不存在任何一组满足题目要求的方案，则输出"no solution"。(不包含引号)