现在有 $ n $ 种角色，每种角色都有 $ m $ 种星级，$ 3 $ 个 $ k $（$k < m$）星级的角色可以合成一个 $ k + 1 $ 星级的角色。每种角色的战力为星级最高的该种角色的战力。总攻击力为为所有角色的战力的总和。你开始时有每种 $1$ 星角色个数各 $ 1 $ 个。

你有 $ A $ 张低级复制卡，效果是生成一个被复制角色的 $ 1 $ 星级同种类角色；$ B $ 张高级复制卡，效果是生成一个被复制角色的同星级同种类角色。

已知星级为 $ i $ 的第 $ j $ 种角色的攻击力为 $ a_{i,j} $（保证对于所有 $ 1 \le i < m$，$a_{i,j} \le a_{i+1,j} $）。复制卡均为消耗品。请问你的总攻击力最多是多少。

第一行输入一个整数 $ T $（$1 \le T \le 100$） 表示数据组数。

对于每组数据，第一行输入四个整数 $ n, m, A, B $（$1 \le n \le 9$，$1 \le m \le 200$，$1 \le A \le 10^{100}$，$1 \le B \le 400$）。

接下来 $ m $ 行每行输入 $ n $ 个整数，第 $ i $ 行第 $ j $ 个整数代表 $ a_{i,j}$（$1 \le a_{i,j} \le 10^9$）。

对于每组数据，输出一行一个正整数表示答案。