← 返回题目列表

Codeforces · 2209/A

A. 人字拖

中文机器翻译题面 查看原题

OtterZ为了增加战斗力,与$$$n$$$怪物进行了战斗。每个怪物的战斗力为$$$a_i$$$,OtterZ的战斗力为$$$c$$$。他有 $$$k$$$ 触发器,可以执行以下操作:

  1. 杀死一个活着的怪物 $$$i$$$ if $$$a_i \le c$$$;那么 $$$c$$$ 变成 $$$c + a_i$$$。
  2. 向活生生的怪物扔人字拖$$$i$$$;触发器会坏,怪物会变得更加愤怒,那么$$$a_i$$$就会变成$$$a_i + 1$$$。
帮助OtterZ在战斗后获得尽可能多的$$$c$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$)。

输出

对于每个测试用例,输出一个整数——最大可能的战斗力。

示例

输入
复制

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

注意

第一次测试中,OtterZ发现了一个强大的怪物并逃跑了,战斗力$$$12$$$。

第六次测试中,OtterZ参与战斗:

  1. 向怪物$$$2$$$扔$$$10$$$人字拖,怪物$$$2$$$战斗力变为$$$12$$$。
  2. 向怪物$$$1$$$扔$$$10$$$人字拖,怪物$$$1$$$战斗力变为$$$11$$$。
  3. 击杀怪物$$$1$$$,OtterZ战力变为$$$29$$$。
  4. 向怪物$$$5$$$扔$$$10$$$人字拖,怪物$$$5$$$战斗力变为$$$12$$$。
  5. 击杀怪物$$$2$$$,OtterZ战力变为$$$41$$$。
  6. 击杀怪物$$$5$$$,OtterZ的战斗力变为$$$53$$$。
  7. OtterZ带着战斗力$$$53$$$逃跑。