3175. [HSOI 2019] HS与小鲜肉

【题目描述】

HSY某宿舍人才辈出，其舍长图书馆男神因被偷拍侧身照而在网络上一票走红。小鲜肉 是HS的好朋友，他也是该宿舍的一员。作为一名著 名的程序设计师，小鲜肉不但注重萌萌哒的外表，还掌握了无数的黑科技。 有一天，小鲜肉制造了一块比特板，这个比特板有$ 2 ^N个$比特元，编号为 $0$~$2 ^N$-$1$ 每个比特元有一个饱和值 $T$，可以接收一个[$0$, $2 ^M$)之间的整数作为输入信号，并 产生整数$ P$ 作为固定的输出信号。当编号为 $i $的比特元接收到输入信号 $j$ 时，将 生成$W(i,j)$枚比特币。 相似的比特元之间还会产生叠加效果。如果两个比特元的编号 $a$ 和 $b $在二进 制下只有一位不同，并且两个比特元中的至少一个接收到的输入信号不小于其饱和值时，这两个比特元将额外生成$ Pa$ $xor$ $Pb$ 枚比特币。小鲜肉希望给每个比特元适 当的输入信号，使比特板生成的比特币总数尽量多。小鲜肉认为这个问题太简单了， 作为一名小鲜肉，比赚钱更重要的是出去赢得无数妹子的目光，所以他把这个问 题交给你解决。

【输入格式】

第一行两个整数$ N$，$M$。 第二行 $2 ^N$个整数$ Ti$，表示每个比特元的饱和值。 第三行 $2 ^N$个整数$ Pi$，表示每个比特元的固定输出信号。 接下来 $2 ^N$行每行$ 2 ^M$个整数$ W(i,j)$，比特币是虚拟货币，所以$ W(i,j)$可能是负数。

【输出格式】

一个整数，表示最多能生成的比特币数。

【样例输入】

3 2 
0 1 1 3 3 0 3 3 
4 8 8 7 0 9 2 9 
-9 -8 3 2 
-9 -6 4 1 
-6 -8 -5 3 
3 -1 -4 -1 
-6 -5 1 10 
-10 7 3 -10
-3 -10 -4 -5 
-2 -1 -9 1 

【样例输出】

133  

【提示】

对于 $20$%的数据，$1 $≤ $n$≤ 3, $1 $≤ $m$ ≤ $2$。

对于另外 $20$%的数据，$Ti$ = $0$ 或 $2 ^m$。

对于另外 $20$%的数据，$m $=$ 1$。

对于 $100$%的数据，$1 $≤ $n $≤ $8$, $1 $≤ $m $≤ $8$, $0 $≤$ Ti $≤ $2 ^m$, $0$ ≤ $Pi$, |$W(i,j)$| ≤ $1024$