该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

为了提高自己的战斗力，翁老师 与 $n$ 只怪兽进行了一场战斗。每只怪兽都有一个战斗力 $a_i$，而 翁老师 有 $c$ 点战斗力。他有 $k$ 只拖鞋，并且每次可以进行如下操作：

• 若 $a_i \le c$，消灭一只存活的怪兽 $i$；然后将 $c$ 变为 $c + a_i$。
• 向一只存活的怪兽 $i$ 投掷一只拖鞋；拖鞋会损坏，并且怪兽将被激怒，其战斗力 $a_i$ 将变为 $a_i + 1$。

请你帮助 翁老师 算出战斗后 $c$ 可以达到的最大值。

输入格式

本题有多组数据

第一行输入一个整数 $t$ 表示测试数据组数。对于每一组数据：

• 第一行包括三个整数 $n$，$c$ 和 $k$。
• 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示战斗力 $c$ 可能的最大值。

10
1 12 23
21
1 8 4
5
1 3 4
16
3 6 3
14 9 11
5 9 2
20 16 18 16 11
5 18 30
1 2 93 84 2
7 29 13
2 9 38 4 7 1 6
10 9 2
8 1 8 11 17 3 14 16 20 10
10 192 109
1 9 20 9 829 3 87 1 283 7
10 1000000000 1000000000
19 1000000000 1 9 2 3 8 1 2 3

12
16
3
6
9
53
109
119
721
3000000048

提示

样例解释

• 在第一组数据中，翁老师 遇到了一只强大的怪物，然后带着 $12$ 点战斗力逃跑。

• 在第六组数据中，翁老师 按照如下流程参与战斗：

  • 向怪兽 $2$ 投掷 $10$ 只拖鞋，使其战斗力变为 $12$。
  • 向怪兽 $1$ 投掷 $10$ 只拖鞋，使其战斗力变为 $11$。
  • 消灭怪兽 $1$，战斗力变为 $29$。
  • 向怪兽 $5$ 投掷 $10$ 只拖鞋，使其战斗力变为 $12$。
  • 消灭怪兽 $2$，战斗力变为 $41$。
  • 消灭怪兽 $5$，战斗力变为 $53$。
  • 带着 $53$ 点战斗力逃跑。

数据范围

对于 $100\%$ 的数据满足：$1\leq t\leq 500$，$1\le n\leq 100$，$0\leq c,k,a_i\leq 10^9$。