18044번 - Polygon 다국어

You are given n segments of lengths ℓ₁, ℓ₂, . . . , ℓ_n, 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 ℓ₁, ℓ₂, . . . , ℓ_n (1 ≤ ℓ_i ≤ 10⁹ ) – 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.