说明

有n 个数a1….an, 你每次可以选择相邻的两个位置i 和j, 如果a_i>0,  就可以使 a_i-1,a_j+1,    你的

目的是经过d 次操作后，使得a1 最大，输出这个最大值。

输入格式

第一行一个整数t(1≤t≤100), 表示有t组数据。

每组数据第一行两个整数，表示n 和d (1 ≤n,d≤200)。

第二行n 个整数，分别表示 ai,a2......,an(0≤ai≤200)

输出格式

t行。每行一个整数表示第t组数据的答案。

3
4 5
1 0 3 2
2 2
100 1
1 8
0

3
101
0