OtterZ为了增加战斗力,与$$$n$$$怪物进行了战斗。每个怪物的战斗力为$$$a_i$$$,OtterZ的战斗力为$$$c$$$。他有 $$$k$$$ 触发器,可以执行以下操作:
- 杀死一个活着的怪物 $$$i$$$ if $$$a_i \le c$$$;那么 $$$c$$$ 变成 $$$c + a_i$$$。
- 向活生生的怪物扔人字拖$$$i$$$;触发器会坏,怪物会变得更加愤怒,那么$$$a_i$$$就会变成$$$a_i + 1$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$c$$$ 和 $$$k$$$ ($$$1 \le n \le 100$$$、$$$0 \le c,k \le 10 ^ 9$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i\le 10 ^ 9$$$)。
输出
对于每个测试用例,输出一个整数——最大可能的战斗力。
示例
输入复制
101 12 23211 8 451 3 4163 6 314 9 115 9 220 16 18 16 115 18 301 2 93 84 27 29 132 9 38 4 7 1 610 9 28 1 8 11 17 3 14 16 20 1010 192 1091 9 20 9 829 3 87 1 283 710 1000000000 100000000019 1000000000 1 9 2 3 8 1 2 3
输出复制
1216369531091197213000000048
注意
第一次测试中,OtterZ发现了一个强大的怪物并逃跑了,战斗力$$$12$$$。
第六次测试中,OtterZ参与战斗:
- 向怪物$$$2$$$扔$$$10$$$人字拖,怪物$$$2$$$战斗力变为$$$12$$$。
- 向怪物$$$1$$$扔$$$10$$$人字拖,怪物$$$1$$$战斗力变为$$$11$$$。
- 击杀怪物$$$1$$$,OtterZ战力变为$$$29$$$。
- 向怪物$$$5$$$扔$$$10$$$人字拖,怪物$$$5$$$战斗力变为$$$12$$$。
- 击杀怪物$$$2$$$,OtterZ战力变为$$$41$$$。
- 击杀怪物$$$5$$$,OtterZ的战斗力变为$$$53$$$。
- OtterZ带着战斗力$$$53$$$逃跑。