← 返回题目列表

Codeforces · 1250/J

J. 游行

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

贝尔兰陆军正在准备大型阅兵。已经决定参加的士兵将被分为$$$k$$$行,并且所有行将包含相同数量的士兵。

当然,并非每种将士兵排列成 $$$k$$$ 行的方式都是合适的。同一排中所有士兵的身高差异不应超过 $$$1$$$。每个士兵的身高是 $$$1$$$ 到 $$$n$$$ 之间的整数。

对于每个可能的高度,您知道具有该高度的士兵的数量。要进行游行,您必须选择参加游行的士兵,然后将所有选定的士兵排列成 $$$k$$$ 行,以便满足以下两个条件:

- 每行都有相同数量的士兵,
- 没有一行包含一对身高相差 $$$2$$$ 或更多的士兵。

计算可以参加阅兵的最大士兵人数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10000$$$) — 测试用例的数量。然后是测试用例。

每个测试用例都以包含两个整数 $$$n$$$ 和 $$$k$$$ 的行开始($$$1 \le n \le 30000$$$, $$$1 \le k \le 10^{12}$$$)——分别是不同身高士兵的数量和游行中士兵的行数。

每个测试用例的第二行(也是最后一行)包含 $$$n$$$ 整数 $$$c_1$$$, $$$c_2$$$, ..., $$$c_n$$$ ($$$0 \le c_i \le 10^{12}$$$),其中 $$$c_i$$$ 是 Berland 身高 $$$i$$$ 的士兵数量军队。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$30000$$$。

输出

对于每个测试用例,打印一个整数——可以参加阅兵的最大士兵数量。

示例

输入 #1

5
3 4
7 1 13
1 1
100
1 3
100
2 1
1000000000000 1000000000000
4 1
10 2 11 1

输出 #1

16
100
99
2000000000000
13

注意

示例测试用例的说明:

1. 行中士兵的身高可以为:$$$[3, 3, 3, 3]$$$, $$$[1, 2, 1, 1]$$$, $$$[1, 1, 1, 1]$$$, $$$[3, 3, 3, 3]$$$(每个列表代表一行);
2.所有士兵可以在同一排行进;
3. 每 $$$3$$$ 行中有 $$$33$$$ 身高 $$$1$$$ 的士兵;
4.所有士兵可以在同一排行进;
5.身高$$$2$$$和$$$3$$$的士兵可以在同一排行进。