#P17950. Soul Link

Soul Link

你是一名法师,需要消灭面前的所有敌人。敌人的等级是 11 到 nn 的整数,等级为 ii 的敌人有 2i−12^{i-1} 点生命值,最初共有 aia_i 个该等级敌人。

你可以使用两种法术:

  • Soul Link(灵魂链接):消耗 mm 点魔力,给一个敌人施加灵魂链接效果,持续到该敌人死亡。
  • Attack(攻击):消耗 11 点魔力,对所有带有灵魂链接效果的敌人各造成 11 点伤害。敌人的生命值变为 00 时死亡,每死亡一个敌人,你获得 mm 点魔力奖励。

可以使用任意多次法术,但魔力在任何时刻都不能小于 00。

求消灭全部敌人所需的最少初始魔力。

输入格式

第一行一个整数 TT(1≤T≤5001\le T\le500),表示测试用例数。

每个测试用例第一行两个整数 n,mn,m(1≤n≤301\le n\le30,1≤m≤10181\le m\le10^{18})。

第二行 nn 个整数 a1,…,ana_1,\ldots,a_n,满足 0≤ai≤1090\le a_i\le10^9 且 ∑ai>0\sum a_i>0。

输出格式

每个测试用例输出一行一个整数,表示最少初始魔力。

样例 1

输入

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

输出

34
48