这是用户在 2024-7-25 16:28 为 https://codeforces.com/contest/1995/problem/B1 保存的双语快照页面，由 沉浸式翻译 提供双语支持。了解如何保存？


B1. Bouquet (Easy Version)
B1. 花束（简易版）
time limit per test
1.5 seconds
每组测试时间限制：1.5 秒
memory limit per test
512 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The only difference is that in this version, the flowers are specified by enumeration.
这是问题的简易版本。唯一的区别在于，本版本中花朵是通过枚举方式指定的。

A girl is preparing for her birthday and wants to buy the most beautiful bouquet. There are a total of n flowers in the store, each of which is characterized by the number of petals, and a flower with k petals costs k coins. The girl has decided that the difference in the number of petals between any two flowers she will use in her bouquet should not exceed one. At the same time, the girl wants to assemble a bouquet with the maximum possible number of petals. Unfortunately, she only has m coins, and she cannot spend more. What is the maximum total number of petals she can assemble in the bouquet?
一个女孩正在为她的生日做准备，想要购买最美丽的花束。商店里总共有 n 朵花，每朵花以其花瓣数量为特征，其中一朵拥有 k 片花瓣的花售价为 k 枚硬币。女孩决定，她花束中任意两朵花的花瓣数量差不能超过一片。同时，她希望组装一个花瓣总数尽可能多的花束。遗憾的是，她只有 m 枚硬币，且不能花费更多。她能组装出的花束中，花瓣总数最多是多少？

ChatGPT 翻译

这是问题的简单版本。唯一的区别在于，本版本中花朵是通过枚举方式指定的。

一个女孩正在为她的生日准备，想要购买最美丽的花束。商店里总共有 n 朵花，每朵花以其花瓣数量为特征，拥有 k 片花瓣的花朵售价为 k 枚硬币。女孩决定，她花束中任意两朵花的花瓣数量之差不能超过一片。同时，她希望组装一个花瓣总数尽可能多的花束。遗憾的是，她只有 m 枚硬币，并且她不能花费更多。请问，她最多能组装多少片花瓣在花束中？

Input

Each test consists of several test cases. The first line contains a single integer t (1≤t≤10000) — the number of test cases. This is followed by descriptions of the test cases.
每个测试由多个测试用例组成。第一行包含一个整数 t （ 1≤t≤10000 ）—— 表示测试用例的数量。接下来是对各个测试用例的描述。

The first line of each test case contains two integers n, m (1≤n≤2⋅105,1≤m≤1018) — the number of flowers in the store and the number of coins the girl possesses, respectively. The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109), where ai is the number of petals of the i-th flower in the store.
每个测试用例的第一行包含两个整数 n 和 m （ 1≤n≤2⋅105,1≤m≤1018 ）——分别表示商店中花的数量和女孩拥有的硬币数量。每个测试用例的第二行包含 n 个整数 a1,a2,…,an （ 1≤ai≤109 ），其中 ai 表示商店中第 i 朵花的瓣数。

The sum of n over all test cases does not exceed 2⋅105.
所有测试用例中 n 的总和不超过 2⋅105 。

ChatGPT 翻译

输入

每个测试包含多个测试用例。第一行包含一个整数 t (1≤t≤10000) —— 测试用例的数量。接下来是各个测试用例的描述。

每个测试用例的第一行包含两个整数 n 和 m (1≤n≤2⋅105,1≤m≤1018) —— 商店中花的数量和女孩拥有的硬币数量。每个测试用例的第二行包含 n 个整数 a1,a2,…,an (1≤ai≤109)，其中 ai 表示商店中第 i 朵花的瓣数。

所有测试用例中 n 的总和不超过 2⋅105。

Output

For each test case, output a single integer — the maximum possible number of petals in the bouquet that the girl can assemble while meeting all the conditions listed above.
对于每个测试案例，输出一个整数——女孩在满足上述所有条件的情况下，能够组装的花束中花瓣的最大可能数量。

ChatGPT 翻译

输出

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

Example
Input
Copy
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
Output
Copy
7
13
610
13
1033
Note

In the first test case, you can assemble a bouquet with (1,1,2,2),(2,2,3),(1,1),(2,2). The maximum over all valid bouquets not greater than 10 is 7 for (2,2,3). In the third test case, you can assemble a bouquet with only one flower of any type, so the answer is 610. In the fourth test case, you can assemble a bouquet with (4,4,5), which gives you 13 petals, and it is the maximum amount of petals that the girl can buy.
在第一个测试案例中，你可以用 (1,1,2,2),(2,2,3),(1,1),(2,2) 组成一束花。所有有效花束中不超过 10 的最大值是 7 ，对应于 (2,2,3) 。在第三个测试案例中，你可以只用一种类型的花组成一束，因此答案是 610 。在第四个测试案例中，你可以用 (4,4,5) 组成一束花，这将给你 13 片花瓣，这是女孩能购买的最大花瓣数量。

ChatGPT 翻译

注释

在第一个测试案例中，你可以组合出以下花束：(1,1,2,2),(2,2,3),(1,1),(2,2)。其中不超过 10 片花瓣的所有有效花束中，最大花瓣数为 7，对应的花束是 (2,2,3)。在第三个测试案例中，你可以只用一种花的一朵花组成花束，因此答案是 610。在第四个测试案例中，你可以组合出 (4,4,5) 的花束，总共有 13 片花瓣，这是女孩能购买到的最大花瓣数量。

fontSizeInput 字体大小输入
自定义测试数据(自动保存)