#2333. 央视娱乐节目购物街—方格取数问题

央视娱乐节目购物街—方格取数问题

说明

在央视娱乐节目购物街中,有这样一个环节,货架上有m×n个方格,在每个方格中各放置1个商品,每个商品都标有价格,嘉宾可以挑选商品,但是选了某一商品,就不能再选它上下左右相邻的商品。最后,挑选出的商品总价最高的人获得胜利。

输入格式

第一行是一个整型数C(C<100)表示共有C组测试数据。

每组测试数据第一行输入货架的行数m和列数n(1<=m,n<=100)。

接下来m行,每行n个数,输入每行每个商品的价值w。(1<=w<=100)。

输出格式

对于每一组输入,输出挑选物品的最大价值。

每组的输出占1行。

样例

2
4 4
10  8   5   2
1   3   9   15
5   10  13  7
24  12  20  14
4 5
12  9   15   4  10
6   2   22   10  8
35   24  3  17  36
20  15  18  14  30
84
158

来源

《趣学算法》7.9节