你正在玩一款冒险游戏。作为一名法师，你需要使用魔法来对付眼前的若干敌人。每个敌人都有一个等级，等级是介于 $1$ 到 $n$ 之间的整数。等级为 $i$ 的敌人拥有 $2^{i-1}$ 点生命值。

你可以使用两种法术：

• 灵魂链接 (Soul Link)：消耗 $m$ 点法力值，对一个敌人施加“灵魂链接”效果。该效果持续到该敌人死亡为止。
• 攻击 (Attack)：消耗 $1$ 点法力值，对所有带有“灵魂链接”效果的敌人造成 $1$ 点伤害，即它们的生命值减少 $1$。一旦某个敌人的生命值降为 $0$，该敌人就会死亡，并且你将获得 $m$ 点法力值作为奖励。

在眼前的敌人中，等级为 $i$ 的敌人有 $a_i$ 个。你可以使用这两种法术任意次，但在任何时候你的法力值都不能小于 $0$。为了击败所有敌人，你最少需要多少初始法力值？

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 500$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n, m$ ($1 \le n \le 30, 1 \le m \le 10^{18}$)，分别表示敌人的最大等级和施放灵魂链接所需的法力值。

第二行包含 $n$ 个正整数。第 $i$ 个整数 $a_i$ 表示等级为 $i$ 的敌人数量。

对于每个测试用例，保证 $0 \le a_i \le 10^9$ 且 $\sum_{i=1}^n a_i > 0$。

输出格式

对于每个测试用例，输出一行包含一个整数，表示击败所有敌人所需的最小初始法力值。

样例

输入样例 1

2
5 7
5 2 4 1 2
6 4
1 1 4 5 1 4

输出样例 1

34
48

说明

第一个测试用例的解释：

起初，有 14 个敌人，生命值分别为 1, 1, 1, 1, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16。

初始拥有 34 点法力值，首先对生命值为 1, 1, 1, 1 的敌人施加灵魂链接，剩余 6 点法力值。

攻击一次，敌人的生命值变为 0, 0, 0, 0, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16。四个敌人死亡，剩余 33 点法力值。

对生命值为 1, 2, 2, 4 的敌人施加灵魂链接，剩余 5 点法力值。

攻击一次，敌人的生命值变为 0, 1, 1, 3, 4, 4, 4, 8, 16, 16。一个敌人死亡，剩余 11 点法力值。

对生命值为 4 的敌人施加灵魂链接，剩余 4 点法力值。

攻击一次，敌人的生命值变为 0, 0, 2, 3, 4, 4, 8, 16, 16。两个敌人死亡，剩余 17 点法力值。

对生命值为 4, 16 的敌人施加灵魂链接，剩余 3 点法力值。

攻击两次，敌人的生命值变为 0, 1, 2, 4, 8, 14, 16。一个敌人死亡，剩余 8 点法力值。

对生命值为 8 的敌人施加灵魂链接，剩余 1 点法力值。

攻击一次，敌人的生命值变为 0, 1, 4, 7, 13, 16。一个敌人死亡，剩余 7 点法力值。

攻击一次，敌人的生命值变为 0, 4, 6, 12, 16。一个敌人死亡，剩余 13 点法力值。

对生命值为 4 的敌人施加灵魂链接，剩余 6 点法力值。

攻击四次，敌人的生命值变为 0, 2, 8, 16。一个敌人死亡，剩余 9 点法力值。

对生命值为 16 的敌人施加灵魂链接，剩余 2 点法力值。

攻击两次，敌人的生命值变为 0, 6, 14。一个敌人死亡，剩余 7 点法力值。

攻击六次，敌人的生命值变为 0, 8。一个敌人死亡，剩余 8 点法力值。

攻击八次，所有敌人死亡，剩余 0 点法力值。