| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 139 | 82 | 73 | 60.833% |
You are given n segments of lengths l1, l2, . . . , ln, respectively. Determine the largest possible circumference of a convex polygon that can be constructed using these segments (in any order, and not neccessarily all of them). The polygon must be non-degenerate – in other words, its area must be positive.
The first line of input contains the number of test cases z (1 ≤ z ≤ 100 000). The test cases follow, each one in the following format:
The first line of a test case contains the number of segments n (1 ≤ n ≤ 100 000). In the second line, there are n integers l1, l2, . . . , ln (1 ≤ li ≤ 109 ) – the lengths of the segments.
The sum of n values over all test cases does not exceed 1 000 000.
For each test case, output a single integer – the largest possible circumference of a convex polygon made of given segments. If no such polygon can be constructed at all, output 0.
4 6 1 2 3 4 5 6 3 9 5 14 4 5 15 4 6 2 10 11
21 0 15 0