| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 2048 MB | 29 | 11 | 9 | 33.333% |
Ivan, Dmitrii, and Pjotr are celebrating Ivan’s birthday at an amusement park with $n$ attractions. The $i$-th attraction operates at minutes $a_i , 2a_i , 3a_i , \dots$ (i.e., every $a_i$ minutes).
Each minute, the friends can either ride exactly one available attraction together or wait. Since the rides are very short, they can board another attraction the next minute. They may ride the attractions in any order.
They want to experience each ride exactly once before heading off to enjoy the birthday cake. What is the earliest time by which they can finish all $n$ attractions?
Each test contains multiple test cases. The first line contains an integer $t$ (1ドル ≤ t ≤ 2000$) — the number of test cases. The descriptions of the $t$ test cases follow.
The first line contains an integer $n$ (1ドル ≤ n ≤ 2000$) — the number of attractions.
The second line contains $n$ integers $a_1, a_2, \dots , a_n$ (1ドル ≤ a_i ≤ 10^9 $) — the values determining when the various attractions operate.
It is guaranteed that the sum of $n$ over all test cases does not exceed 2000ドル$.
For each test case, print the earliest time the three friends can finish all $n$ attractions.
3 4 1 2 3 4 4 1 1 1 1 6 1 2 1 2 2 2
4 4 8
In the first test case, the three friends can ride the $i$-th attraction at the $i$-th minute. Since there are 4ドル$ attractions, they need 4ドル$ minutes to ride them all.
In the third test case, the three friends can ride the attractions in order at minutes 1ドル,ドル 2ドル,ドル 3ドル,ドル 4ドル,ドル 6ドル,ドル 8ドル$ respectively. Therefore, they can ride all attractions in 8ドル$ minutes. One can show that it is impossible to finish all the attractions earlier.