P12804 [AMPPZ 2019] Polygon

**Time limit:** 1s, **memory limit:** 512MB

You are given $n$ segments of lengths $\ell_1, \ell_2, \ldots, \ell_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 \le z \le 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 \le n \le 100\,000$). - In the second line, there are $n$ integers $\ell_1, \ldots, \ell_n$ ($1 \le \ell_i \le 10^9$) – 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$.