描述

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

输入格式

第一行两个整数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。

样例解释

输入信号依次为2 2 3 0 3 1 0 3。