Description

为了打 boss，J 需要先在一片条状蓝莓田中采摘蓝莓，收集能量。蓝莓田可 以分为 n 块，每块中蓝莓总重为 a[i]。贪婪的 J 在选择某块后一定会把蓝莓全 部摘完。但由于某些原因，J 不能把相邻两块上的蓝莓都摘完。另外，J 的能力 有限，最多只能拿走重量为 m 的蓝莓。贪婪的 J 想知道，他最多可以拿走多少蓝 莓。

Format

Input

第一行一个数 T，表示 T 组数据

接下来每组数据，第一行两个数 n,m，第二行 n 个数表示 a 数组

Output

T 行，每行一个数表示答案

Samples

2
5 100
50 10 20 30 40
5 87
21 45 30 12 14

90
65

Sample Descriptions

第 1 组样例中，选取 1,3,5 三块地，则总重超过 m，不合法。只能选取 1,5 两块地，总重为 90，是最优方案

第 2 组样例中，选取 1,3,5 三块地的方案最优

Limitation

100%的数据 T≤100，n,m≤1000