问题1229--值钱的项链

1229: 值钱的项链

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

题目描述

一条项链,有n个位置可以串珠子,从1到n形成一个环,对于1<=i<n,第i个位置和第i+1个位置相邻,同时第1个位置和第n个位置相邻,每一个位置都要从m个备选的珠子中选择一个(对于不同的位置,备选的珠子不同),序号从1到m
每个珠子都有自己的价值和颜色,珠子有两种颜色,红色和蓝色,项链不能存在两个连续的红色珠子,要使得串起来的项链总价值最大,输出最大的总价值,如果不存在合法的方案,输出-1

输入

第一行一个整数T(1<=T<=10000),表示数据组数
对于每一组数据,第一行两个整数n和m
接下来n行,每行m个整数,第i行的第j个整数表示第i个位置的第j颗备选珠子的价值val(0<=val<=1e9)
再接下来n行,每行m个整数,第i行的第j个整数表示第i个位置的第j颗备选珠子的颜色color(红色为1,蓝色为0)
保证Σ(n*m)<=1e6

输出

输出T行,每行一个整数,表示项链的最大价值,如果不存在合法的方案,输出-1

样例输入 Copy

2
2 2
4 5
8 2
1 0
0 1
2 2
4 5
8 2
1 1
1 1

样例输出 Copy

13
-1