#10089. [Sleeping Cup #9] C. 2048: Python vs. OOM

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');
}

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

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

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

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

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

本题有多组测试数据。

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

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

第一行输入四个正整数 。

第二行输入 个正整数 。

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

样例输入

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

样例解释

除了数据的生成方式不符合规定以外，前 5 组测试数据依次满足子任务 1 中 5 个测试点的特殊限制。

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

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

数据范围

对于所有子任务：

• 。
• 。
• 。

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

1. 本子任务保证：
   • 。
   • 评测时使用的每组测试数据均按照下列给定的生成方式生成。
   • 本子任务包含恰好 5 个测试点，每个测试点的额外特殊限制和对应的测试数据生成方式如下：
     1. 对于所有的 ，：
        • 令 ，对于每组测试数据：
          • 在 中均匀随机生成 。
          • 在 中均匀随机生成 。
          • 在 中均匀随机生成 。
          • 在 的因数中均匀随机生成 。
          • 令 。
          • 对于所有的 ，在 中均匀随机生成 。
     2. 是 的倍数：
        • 令 ，对于每组测试数据：
          • 在 中均匀随机生成 。
          • 在 中均匀随机生成 。
          • 在 中均匀随机生成 。
          • 在 中均匀随机生成 。
          • 令 。
          • 对于所有的 ，在 中均匀随机生成 。
     3. ：
        • 令 ，对于每组测试数据：
          • 在 中均匀随机生成 。
          • 在 中均匀随机生成 。
          • 在 中均匀随机生成 。
          • 令 。
          • 对于所有的 ，在 中均匀随机生成 。
     4. ：
        • 令 ，对于每组测试数据：
          • 在 中均匀随机生成 。
          • 在 中均匀随机生成 。
          • 在 中均匀随机生成 。
          • 令 。
          • 对于所有的 ，在 中均匀随机生成 。
     5. ：
        • 令 ，对于每组测试数据：
          • 在 中均匀随机生成 。
          • 在 中均匀随机生成 。
          • 在 中均匀随机生成 。
          • 令 。
          • 对于所有的 ，在 中均匀随机生成 。
2. 。
3. 。
4. 无特殊限制。

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