#P18385. Sticks 2

Sticks 2

Sticks 2

有 nn 根木棍,第 ii 根长度为 2ai2^{a_i}。你可以任意重排这些木棍,然后按该顺序从左向右放在数轴上。设重排后的第 ii 根木棍占据区间 [li,ri][l_i,r_i],合法放置必须满足:

  • l1≥ml_1\ge m;
  • ri=li+2air_i=l_i+2^{a_i};
  • lil_i 是 2ai2^{a_i} 的整数倍;
  • ri≤li+1r_i\le l_{i+1},木棍之间允许有空隙。

对一个固定的排列,定义 ff 为所有合法放置中 rnr_n 的最小值。也就是该排列下,每根木棍都尽可能早地放置时得到的最终右端点。

求所有重排方案中 ff 的最大值。这里最大化的是“每个排列各自能达到的最小右端点”;不能把木棍随意右移来增大答案。

输入格式

第一行一个整数 T≥1T\ge1,表示测试用例数。

每组第一行两个整数 n,mn,m,第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。所有整数都采用十进制表示,包括可能超过64位整数范围的 mm。

  • 1≤n≤2⋅1051\le n\le2\cdot10^5;
  • 0≤m<21000\le m<2^{100};
  • 0≤ai<1000\le a_i<100;
  • 全部测试用例的 nn 之和不超过 2⋅1052\cdot10^5。

输出格式

每组输出一行一个十进制整数,表示最大可能的 ff。答案可能超过64位整数范围。

样例输入 1

2
3 0
1 2 3
5 14
0 2 2 3 3

样例输出 1

20
52

样例说明

第一组把长度排为 2,8,42,8,4,最早放置的区间依次为 [0,2][0,2]、[8,16][8,16]、[16,20][16,20],最优答案为20。

第一组样例的木棍放置图

第二组可以按长度 4,8,1,8,44,8,1,8,4 放置,最早放置的区间依次为 [16,20][16,20]、[24,32][24,32]、[32,33][32,33]、[40,48][40,48]、[48,52][48,52],答案为52。

第二组样例的木棍放置图