← 返回题目列表

Codeforces · 2068/K

K. 游乐园游乐设施

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

Ivan、Dmitrii 和 Pjotr​​ 正在一个拥有 $$$n$$$ 景点的游乐园庆祝 Ivan 的生日。第 $$$i$$$ 个景点的运营时间为 $$$a_i、2a_i、3a_i、\dots$$$ 分钟(即每 $$$a_i$$$ 分钟)。

每分钟,朋友们只能乘坐一个可用的景点 一起 或等待。由于行程很短,他们下一分钟就可以登上另一个景点。他们可以按任何顺序游览景点。

他们想在出发去享受生日蛋糕之前将每次骑行体验一次。他们最早可以完成所有 $$$n$$$ 景点的时间是多少?

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 2000$$$) — 测试用例的数量。 $$$t$$$ 测试用例的描述如下。

第一行包含一个整数 $$$n$$$ ($$$1\le n \le 2000$$$) — 景点的数量。

第二行包含 $$$n$$$ 整数 $$$a_1,\, a_2,\,\ldots,\, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 确定各个景点何时运行的值。

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

输出

对于每个测试用例,打印三个朋友完成所有 $$$n$$$ 景点的最早时间。

示例

输入
复制

3
4
1 2 3 4
4
1 1 1 1
6
1 2 1 2 2 2

输出
复制

4
4
8

注意

在 第一个测试用例,三个朋友可以在第$$$i$$$第$$$i$$$分钟乘坐第$$$i$$$个景点。由于有 $$$4$$$ 个景点,他们需要 $$$4$$$ 分钟才能游完所有景点。

在 第三个测试用例,三个朋友分别可以$$$1,\, 2,\, 3,\, 4,\, 6,\, 8$$$分钟依次乘坐景点。因此,他们可以在 $$$8$$$ 分钟内游完所有景点。可见,要早点走完所有景点是不可能的。