注意

本题需要文件读写（python.in / python.out）。

本题中（所有操作结束后的）$\displaystyle \bm{b_1 + b_2 + \ldots + b_n}$ 的值超过了 64 位有符号整数（以及 64 位无符号整数）的存储范围，建议使用 C++14（或更高版本）中引入的 __int128 扩展数据类型进行存储。请注意，不要使用 __int128 类型的变量（或常量）作为参数调用 cmath（math.h）库中的函数（如绝对值函数 abs，算术平方根函数 sqrt 等），否则可能会导致编译错误。

你可以使用以下代码（使用时需要包含 <cstdio> 或 <bits/stdc++.h> 头文件），并用 read() 读入一个 __int128 类型的正整数，用 writeline(x) 输出一行一个 __int128 类型的非负整数 $\bm x$。请注意，不要将以下代码和其他输入输出方式混用：

inline __int128 read()
{
	__int128 x = 0;
	char c = getchar_unlocked();
	while (c < '0') c = getchar_unlocked();
	while (c >= '0')
	{
		x = x * 10 + c - '0';
		c = getchar_unlocked();
	}
	return x;
}
void write(__int128 x)
{
	if (x <= 9)
	{
		putchar_unlocked(x + '0');
		return;
	}
	write(x / 10);
	putchar_unlocked(x % 10 + '0');
}
inline void writeline(__int128 x)
{
	write(x);
	putchar_unlocked('\n');
}

题目背景

TouchFish 是一款专为局域网环境打造的轻量级聊天软件 —— 在学校机房等断网环境下，传统的 QQ、微信等聊天工具无法使用，TouchFish 应运而生。它只需要局域网就能工作，也可在公网使用。

（资料来源：https://touchfish.ilovescratch.us.ci/guide/）

2048 年 3 月 1 日，局域网聊天工具 TouchFish 发行了新的服务端程序版本 v32.0.0，增加了一个名叫「摸鱼天地」的新功能。该功能允许用户使用 Python v6.0.0 及以上版本编写自己的游戏，将其上传到服务端，并通过调用 TouchFish API v10.0.0 自动完成社区构建、新手引导文档编写、游戏数值优化甚至游戏 AI 训练等一系列游戏开发任务。

2048 年最适合玩的游戏当然是「2048」了！在传统的「2048」中，玩家被要求在一个 $4$ 行 $4$ 列的网格中通过改变重力方向合并不断出现的数字方块 $2 = 2^1$ 或 $4 = 2^2$，最终在网格被填满且无法合并更多方块前得到数字 $2048 = 2^{11}$。于是，Sleeping Iguana 使用 Python v6.0.0 编写了一个简单的「2048」游戏，并利用 TouchFish API v10.0.0 实现了远多于原版「2048」游戏的趣味机制，包括但不限于动态网格大小、闯关模式、双人游戏模式等。

题目描述

Sleeping Iguana 正在测试它的「2048」游戏，现在它玩到了一个奖励关！它的网格上目前有 $n$ 个数字方块，其中第 $i$ 个方块上的数字是 $2^{b_i}$。

在这个奖励关中，Sleeping Iguana 需要施展 $k$ 次魔法，每次魔法中它需要选择 $m$ 个不同的数字方块，并将选中的每个方块上的数字都乘上 $2^a$。

由于大的数字非常稀有，Sleeping Iguana 本想每次都选取数字最大的 $m$ 个方块，但它突然意识到一个问题：由于内存条价格居高不下，为了节省开支，服务端的内存配置小得可怜 —— 它绝不能让游戏出现 OOM（Out of memory，内存不足）的错误，否则服务端的所有者会找它麻烦。

根据游戏的源代码，方块上的数字在 Python v6.0.0 中是以长度为 $n$ 的列表存储的，存储该列表花费的内存字节数为：

$$S = 4 \cdot \sum _{i = 1} ^n \left \lfloor \dfrac{b_i}{30} \right \rfloor + 36n + 56$$

为了防止 OOM，Sleeping Iguana 希望奖励关结束后存储列表花费的内存字节数最小，那么这个最小值是多少？

输入格式

本题有多组测试数据。

第一行输入一个正整数 $T$，表示测试数据的数量。

接下来，对于每组测试数据：

第一行输入四个正整数 $n, m, k, a$。

第二行输入 $n$ 个正整数 $b_1, b_2, \ldots, b_n$。

输出格式

对于每组测试数据，输出一行一个正整数表示奖励关结束后存储列表花费的内存字节数的最小数量。

样例

6
6 4 7 3
8 6 7 1 2 6
8 5 9 300
115 123 255 179 35 64 129 128
4 4 8 16
94 87 204 20
7 3 1 49
335 69 185 442 656 299 883
9 1 10000 6677
2551 538 2865 848 2239 1823 2162 2636 2533
5 2 6 11
23 27 28 31 40

272
2268
316
688
8905440
256

样例解释

本样例将作为子任务 4 的首个测试点参与评测。

前 5 组测试数据依次满足子任务 1 中 5 个测试点的特殊限制。

对于第 6 组测试数据，一种最优的操作方案为：

操作次序	选择的方块编号	方块上的数字
$0$	$/$	$[2^{23}, 2^{27}, 2^{28}, 2^{31}, 2^{40}]$
$1$	$1, 5$	$[2^{34}, 2^{27}, 2^{28}, 2^{31}, 2^{51}]$
$2$		$[2^{45}, 2^{27}, 2^{28}, 2^{31}, 2^{62}]$
$3$		$[2^{56}, 2^{27}, 2^{28}, 2^{31}, 2^{73}]$
$4$		$[2^{67}, 2^{27}, 2^{28}, 2^{31}, 2^{84}]$
$5$	$1, 4$	$[2^{78}, 2^{27}, 2^{28}, 2^{42}, 2^{84}]$
$6$		$[2^{89}, 2^{27}, 2^{28}, 2^{53}, 2^{84}]$

Python 6.0.0 (tags/v6.0.0:25e3198, Oct  8 2047, 13:17:30) [MSC v.1944 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> array = [2**89, 2**27, 2**28, 2**53, 2**84]
>>> size = sys.getsizeof(array) + sum([sys.getsizeof(x) for x in array])
>>> print(size)
256

数据范围

对于所有子任务：

• $1 \le T \le 30$。
• $1 \le m \le n \le 30$。
• $1 \le b_i, a, k \le 10^9$。

本题共有 4 个等分的子任务，各子任务的特殊限制如下：

1. 本子任务保证：
   • $k \le 10^4$。
   • 评测时使用的每组测试数据均从所有合法的测试数据中等概率抽取。
   • 本子任务包含恰好 5 个测试点，每个测试点的额外特殊限制如下：
     1. 对于所有的 $1 \le i \le n$，$b_i + ak < 30$。
     2. $a$ 是 $30$ 的倍数。
     3. $m = n$。
     4. $k = 1$。
     5. $m = 1$。
2. $k \le 60$。
3. $2m \le n$。
4. 无特殊限制。

其中子任务 4 依赖于其他所有子任务。