Oden VS Genshin Impact

Problem Description

现在有 $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}$）。复制卡均为消耗品。请问你的总攻击力最多是多少。

Input

第一行输入一个整数 $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$）。

Output

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

Sample Input

2
3 3 3 3
1 2 3
4 5 6
7 8 9
3 1 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 399
998244353 998244853 998442353

Sample Output

15
2994931559

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（10）