#P1422. MC陷阱大师

MC陷阱大师

MC陷阱大师

时间限制: 1s

空间限制:256MB

Description

有一天晚上 xtxt 在玩 MC ,已知 xtxtXX 点HP,且携带了 kk 个不死图腾( HP=0HP=0 后将 HPHP 重置为2020 ),他不小心闯进了某个矩阵陷阱,陷阱的每个格子都摆放了一件物品,每件物品都有一个 EMCEMC 值, xtxt 在进入一个格子后会触发一条指令,强制令其获得该物品,然后将此值与他的 HPHP 异或,并将结果记为其 HPHPHP=0HP=0 后死亡,求 xtxt 走出陷阱后所能获得的物品的 EMCEMC 值之和的最大值。

Input Format

第一行包括两个整数 XX, kk , 表示初始有 XX 点HP,kk 个不死图腾,用空格分隔。

第二行包括两个整数 nn, mm,表示矩阵的大小,用空格分隔。

33 ~ n+2n+2 行,每行 mm 个整数,表示格子内物品的EMCEMC

Output Format

输出一个整数,表示获得的物品的 EMCEMC 值之和的最大值,若xtxt无法走出陷阱,输出1-1

Input Example

20 0
3 3
1 2 3
4 5 6
7 8 -1

Output Example

36

Data Range

  • 1nm61k101\leq n,m\leq6,1 \leq k \leq 10
  • 1X,EMC1e81\leq X , EMC \leq 1e8

Note

  • 起点(0000
  • 出口无物品且 以1-1为标志(即格子内数值为-1)。