CF2068K.Amusement Park Rides

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

Ivan、Dmitrii 和 Pjotr 正在一个有 $n$ 个游乐设施的游乐园庆祝 Ivan 的生日。第 $i$ 个设施会在每分钟 $a_i, 2a_i, 3a_i, \dots$ （即每隔 $a_i$ 分钟）运行一次。

每分钟，三位朋友可以选择一起乘坐一个可用的设施或等待。由于设施运行时间极短，他们可以在下一分钟立即乘坐其他设施。他们可以按任意顺序乘坐设施。

他们希望在享用生日蛋糕前体验所有设施各一次。求他们完成所有 $n$ 个设施的最早时间。

每个测试包含多个测试用例。第一行包含整数 $t$ （ $1 \le t \le 2000$ ）——测试用例数量。接下来是各测试用例的描述。

每个测试用例的第一行包含整数 $n$ （ $1 \le n \le 2000$ ）——游乐设施数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $1 \le a_i \le 10^9$ ）——决定各设施运行时间的参数。

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

对于每个测试用例，输出三位朋友完成所有设施的最早时间。

输入#1

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

输出#1

4
4
8

第一个测试用例中，三人可以在第 $i$ 分钟乘坐第 $i$ 个设施。由于共有 $4$ 个设施，总时间为 $4$ 分钟。

第三个测试用例中，三人按顺序在第 $1, 2, 3, 4, 6, 8$ 分钟乘坐设施，总时间为 $8$ 分钟。可以证明无法更早完成。

翻译由 DeepSeek R1 完成

输入解题思路，AI测评打分。不知道怎么写?