题目描述

「魈」也想长高高，请你帮帮他！

「魈」从起点出发，想要到达终点，沿途有若干的 buff 或是 深坑。用 ai 表示第 i 个遇到特殊事件为 buff或深坑。

若 ai≥0 ，表示第 i 个遇到的为 buff，可以帮助「魈」的身高提高 ai 。若 ai<0 ，则表示第 i 个遇到的是深度为 −ai 的 深坑，若此时「魈」的身高 h 大于 −ai （即大于坑的深度），则可直接越过这个坑，若 h 小于等于 −ai ，则「魈」会因为掉入坑中导致身高减半（即 h′=⌊h2⌋ ）。但「魈」有 k 次使用 「风轮两立」的机会，可以不用考虑身高直接跳过一个 深坑。

测试数据保证每组数据中 ai<0 的个数不超过 $2×10^3$ 。

当「魈」的身高变为 0 时，将直接失败，无法到达终点。现给出「魈」的初始身高 h ，和沿途会遇到的 n 个 buff 或 深坑，请你求出「魈」在到达终点时的最高身高，若无论如何都无法到达终点，则输出 −1 。

输入 第一行为数据组数 T (1≤T≤10) 。

接下来 T 组数据：

第一行三个整数 n,k,h $(1≤n≤10^6,0≤k≤2×10^3,1≤h≤10^3)$ ，分别表示沿途会遇到的 n 个特殊事件，最多可使用「风轮两立」的次数和「魈」的初始身高。

第二行 n 个整数 ai ($−10^3≤ai≤10^3$) ，表示沿途遇到的 buff 或 深坑。

输出

对于每组数据，输出一行一个正整数，表示到达终点时能达到的最高身高，若无法到达输出 −1。

输入样例

3
4 1 10
-10 -5 1 2
3 0 1
-1 1 2
5 2 1
-1 2 -3 5 -10

输出样例

13
-1
6