Sticks 2
有 n 根木棍,第 i 根长度为 2ai。你可以任意重排这些木棍,然后按该顺序从左向右放在数轴上。设重排后的第 i 根木棍占据区间 [li,ri],合法放置必须满足:
- l1≥m;
- ri=li+2ai;
- li 是 2ai 的整数倍;
- ri≤li+1,木棍之间允许有空隙。
对一个固定的排列,定义 f 为所有合法放置中 rn 的最小值。也就是该排列下,每根木棍都尽可能早地放置时得到的最终右端点。
求所有重排方案中 f 的最大值。这里最大化的是“每个排列各自能达到的最小右端点”;不能把木棍随意右移来增大答案。
输入格式
第一行一个整数 T≥1,表示测试用例数。
每组第一行两个整数 n,m,第二行 n 个整数 a1,…,an。所有整数都采用十进制表示,包括可能超过64位整数范围的 m。
- 1≤n≤2⋅105;
- 0≤m<2100;
- 0≤ai<100;
- 全部测试用例的 n 之和不超过 2⋅105。
输出格式
每组输出一行一个十进制整数,表示最大可能的 f。答案可能超过64位整数范围。
样例输入 1
2
3 0
1 2 3
5 14
0 2 2 3 3
样例输出 1
20
52
样例说明
第一组把长度排为 2,8,4,最早放置的区间依次为 [0,2]、[8,16]、[16,20],最优答案为20。

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