时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
一条项链，有n个位置可以串珠子。这n个珠子形成一个环，也就是说，当
时，对于
，第i个位置和第i+1个位置相邻，同时第1个位置和第n个位置也相邻。
现在，每一个位置都要从m个备选的珠子中选择一个（对于不同的位置，备选的珠子不同）。每个珠子都有自己的价值和颜色。珠子的颜色分为两种：红色和蓝色。项链中不能存在两个连续的红色珠子。现在，Miaoyao想要使串起来的项链总价值最大，请求出最大的总价值。如果不存在合法的方案，输出-1。输入描述:
第一行一个整数T，表示数据组数。
对于每一组数据，第一行两个整数n和m，含义如题目中所述。
接下来n行，每行m个整数，第i行的第j个整数表示第i个位置的第j颗备选珠子的价值。
再接下来n行，每行m个整数，第i行的第j个整数表示第i个位置的第j颗备选珠子的颜色（红色为1，蓝色为0）。
保证
输出描述:
输出T行，每行一个整数，表示项链的最大价值，如果不存在合法的方案，输出-1