← 返回题目列表

Codeforces · 1995/B1

B1. 花束(简单版)

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

这是问题的简单版本。唯一的区别是,在这个版本中,花是通过枚举指定的。

一个女孩正在准备她的生日,想要买一束最美丽的花束。商店里一共有$$$n$$$朵花,每朵花的特征是花瓣的数量,一朵有$$$k$$$花瓣的花需要$$$k$$$金币。女孩决定她在花束中使用的任何两朵花之间的花瓣数量差异不应超过一朵。与此同时,女孩想要组装一束花瓣数量尽可能多的花束。不幸的是,她只有 $$$m$$$ 硬币,而且她不能花更多。她最多可以在花束中组装多少片花瓣?

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) - 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5, 1 \le m \le 10^{18}$$$) - 分别是商店中鲜花的数量和女孩拥有的硬币数量。每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是商店中第 $$$i$$$ 朵花的花瓣数。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot {10}^5$$$。

输出

对于每个测试用例,输出一个整数——女孩在满足上述所有条件的情况下可以组装的花束中花瓣的最大可能数量。

示例

输入 #1

5
5 10
1 1 2 2 3
8 20
4 2 7 5 6 1 1 1
8 100000
239 30 610 122 24 40 8 2
11 13
2 4 11 1 1 2 3 5 4 3 2
8 1033
206 206 206 207 207 207 207 1000

输出 #1

7
13
610
13
1033

注意

在第一个测试用例中,您可以用 $$$(1, 1, 2, 2), (2, 2, 3), (1, 1), (2, 2)$$$ 组装花束。 $$$(2, 2, 3)$$$ 的所有有效花束不超过 $$$10$$$ 的最大值为 $$$7$$$。在第三个测试用例中,您可以仅用一朵任意类型的花组装一束花,因此答案是 $$$610$$$。在第四个测试用例中,您可以用$$$(4, 4, 5)$$$组装一束花束,这将为您提供$$$13$$$花瓣,这是女孩可以购买的最大花瓣数量。